글 읽기 - 17524문제 반례를 알고 싶습니다.

iqeq1989 2년 전 0

k의 경우를 3개로 나누어 풀었습니다.

옷의 온도가 낮은 경우부터 차례대로 따져주었고, continue인 경우도 따져주어 코드를 짰는데 어떤 반례가 있을지 의문이 듭니다.

49번 째줄이 문제였습니다.

2 3

40 1

41 1

==> 31

2 3

40 1

50 10

==> 60

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
vector<pair<ll, ll>>v;
int n, k;

int main() {
	ios_base::sync_with_stdio(0);
	cout.tie(0); cin.tie(0);

	cin >> n >> k;
	v.resize(n);
	for (int i = 0; i < n; i++) {
		ll t, w;
		cin >> t >> w;
		v[i] = { t,w };
	}
	sort(v.begin(), v.end());
	if (k == 1) {
		int T = v[0].first;
		ll sum = 0;
		for (int i = 0; i < n; i++) {
			sum = max(sum, 30 + (v[i].first - T) * v[i].second);
		}
		cout << sum << '\n';
	}
	else if (k == 2) {
		int T1 = v[0].first;
		ll ans = 1234567890;
		for (int T2 = T1; T2 <= 100; T2++) {
			ll tmp1 = 30;
			ll tmp2 = 0;
			for (int i = 1; i < n; i++) {
				if ((v[i].first >= T1 && 30 + (v[i].first - T1) * v[i].second <= tmp1) || (v[i].first >= T2 && 30 + (v[i].first - T2) * v[i].second <= tmp2)) continue;
				if (v[i].first < T2) {
					tmp1 = max(tmp1, 30 + (v[i].first - T1) * v[i].second);
				}
				else {
					tmp2 = max(tmp2, 30 + (v[i].first - T2) * v[i].second);
				}
			}
			ans = min(ans, tmp1 + tmp2);
		}
		cout << ans << '\n';
	}
	else {
		if (n <= 3) {
			cout << 30 << '\n'; return 0;
		}
		int T1 = v[0].first;
		ll ans = 1234567890;
		for (int T2 = T1; T2 <= 100; T2++) {
			for (int T3 = T2; T3 <= 100; T3++) {
				ll tmp1 = 30;
				ll tmp2 = 0;
				ll tmp3 = 0;
				for (int i = 1; i < n; i++) {
					if ((v[i].first >= T1 && 30 + (v[i].first - T1) * v[i].second <= tmp1) || (v[i].first >= T2 && 30 + (v[i].first - T2) * v[i].second <= tmp2) || (v[i].first>=T3&&30 + (v[i].first - T3) * v[i].second <= tmp3)) continue;
					if (v[i].first < T3) {
						if (v[i].first < T2) {
							tmp1 = max(tmp1, 30 + (v[i].first - T1) * v[i].second);
						}
						else {
							if (30 + (v[i].first - T1) * v[i].second <= tmp1 || 30 + (v[i].first - T2) * v[i].second <= tmp2) continue;
							tmp2 = max(tmp2, 30 + (v[i].first - T2) * v[i].second);
						}
					}
					else {
						tmp3 = max(tmp3, 30 + (v[i].first - T3) * v[i].second);
					}
				}
				ans = min(ans, tmp1 + tmp2 + tmp3);
			}
		}
		cout << ans << '\n';
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

17524문제 반례를 알고 싶습니다.

iqeq1989 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말