글 읽기 - 반례나 틀린 부분 부탁드립니다...

kth990303 3년 전 0

38~43번째 줄 주석친 부분을 코드에 포함시키면 틀렸다고 뜹니다.

TC #2

4
10000 3000
6000 2000
3000 3001
5000 10000

ans: Kkeo-eok

TC #2-1

3
100 100
10 200
100 10
ans: Kkeo-eok

TC #2-1를 예로 들어, 두번째 대회를 아예 미참여하면 첫번째, 세번째 대회는 참여가 가능하므로 Kkeo-eok이고, 이렇게 중간에 대회를 건너뛰는 경우 때문에 38~43번째 줄을 추가했는데도 틀렸다고 뜹니다.. 어디가 틀렸는지 모르겠네요..

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
vector<pair<ll, ll>> v;
ll d[100001];
ll dp[100001];
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		ll limit, m;
		cin >> limit >> m;
		v.push_back({ limit, m });
		d[i] = m;
	}
	if (n <= 2) {
		cout << "Kkeo-eok";
		return 0;
	}
	int cnt = 0;
	ll max_idx = 0;
	ll max_money = 0;
	for (int i = 0; i < n - 1; i++) {
		if (dp[i] + d[i] <= v[i + 1].first) {
			dp[i + 1] += dp[i] + d[i];
			if (max_money < d[i]) {
				max_idx = i;
				max_money = d[i];
			}
		}
		else {
			if (cnt == 0 && i<n-2 && dp[i] + d[i] <= v[i + 2].first && dp[i] + d[i] > v[i + 1].first) {
				cnt++;
				dp[i + 1] = dp[i] + d[i];
				i++;
				continue;
			}
			if (max_money < d[i]) {
				max_idx = i;
				max_money = d[i];
			}
			if (cnt == 0 && i != 0 && dp[i] - d[max_idx] + d[i] <= v[i + 1].first) {
				cnt++;
				dp[i + 1] = dp[i] - d[max_idx] + d[i];
				continue;
			}
			dp[i + 1] = dp[i];
			cnt++;
		}
	}
	if (cnt > 1)
		cout << "Zzz";
	else
		cout << "Kkeo-eok";
	return 0;
}

surung9898 3년 전 2

반례는 다음과 같습니다.

/*
6
0 3
4 5
9 5
4 2
13 2
12 3

answer: Zzz
output: Kkeo-eok

kth990303 3년 전 0

정말 감사합니다

덕분에 드디어 완벽하게 푼 것 같네요

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

문제

문제

출처

ICPC

반례나 틀린 부분 부탁드립니다...

kth990303 3년 전 0

surung9898 3년 전 2

kth990303 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말