oj.uz

Submission #137530

# Submission time Handle Problem Language Result Execution time Memory
137530 2019-07-28T06:10:17 Z 임유진(#3281) Coins (BOI06_coins) C++14
90 / 100
 114 ms 6268 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 <= N; 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" << min(K - dp[i - 1], K - 1);
			return 0;
		}
	}

	int cnt = 0;
	for(int i = 0; i < N; i++) if(!D[i]) cnt++;
	cout << cnt << "\n" << K - dp[N];
	return 0;
}

Subtask #1
90.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 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 105 ms 6204 KB Output is correct
8 Correct 105 ms 6136 KB Output is correct
9 Correct 114 ms 6136 KB Output is correct
10 Correct 113 ms 6268 KB Output is correct