oj.uz

답안 #137531

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137531 2019-07-28T06:11:35 Z 임유진(#3281) Coins (BOI06_coins) C++14
90 / 100
 112 ms 6312 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" << min(K - dp[i - 1], K - 1);
			return 0;
		}
	}
}

Subtask #1
90.0 / 100.0

# 결과 실행 시간 메모리 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 504 KB Output is correct
7 Correct 105 ms 6136 KB Output is correct
8 Correct 105 ms 6312 KB Output is correct
9 Correct 112 ms 6244 KB Output is correct
10 Correct 109 ms 6140 KB Output is correct