oj.uz

Submission #137532

# Submission time Handle Problem Language Result Execution time Memory
137532 2019-07-28T06:12:37 Z 임유진(#3281) Coins (BOI06_coins) C++14
80 / 100
 113 ms 6264 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long lint;

const int MAXN = 500005;

lint C[MAXN];
int D[MAXN];
lint dp[MAXN];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N;
	lint K;

	cin >> N >> K;
	for(int i = 0; i < N; i++) cin >> C[i] >> D[i];
	
	int k = 0;
	for(int i = 1; ; i++) {
		lint t = dp[i - 1];
		while(true) {
			while(k < N && D[k]) k++;
			if(k == N) break;
			while(k < N - 1 && D[k + 1] && t + C[k] >= C[k + 1]) {
				t += C[k];
				k++;
			}
			if(k < N - 1 && !D[k + 1] && t + C[k] >= C[k + 1]) {
				t = dp[i - 1];
				k++;
				continue;
			}
			dp[i] = t + C[k++];
			break;
		}
		if(dp[i] == 0 || dp[i] >= K) {
			cout << i - 1 << "\n" << K - dp[i - 1];
			return 0;
		}
	}
}

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 106 ms 6168 KB Output is correct
8 Incorrect 106 ms 6264 KB Output isn't correct
9 Correct 113 ms 6200 KB Output is correct
10 Correct 110 ms 6264 KB Output is correct