oj.uz

Submission #137543

# Submission time Handle Problem Language Result Execution time Memory
137543 2019-07-28T06:23:14 Z 임유진(#3281) Coins (BOI06_coins) C++14
100 / 100
 112 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++) {
		while(true) {
			while(k < N && D[k]) k++;
			if(k == N) break;
			if(k < N - 1 && dp[i - 1] + C[k] >= C[k + 1]) {
				k++;
				continue;
			}
			dp[i] = dp[i - 1] + C[k++];
			break;
		}
		if(dp[i] == 0 || dp[i] >= K) {
			cout << i - 1 << "\n" << min(K - dp[i - 1], K - 1);
			return 0;
		}
	}
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is 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 106 ms 6264 KB Output is correct
8 Correct 105 ms 6264 KB Output is correct
9 Correct 112 ms 6136 KB Output is correct
10 Correct 109 ms 6264 KB Output is correct