oj.uz

Submission #137542

# Submission time Handle Problem Language Result Execution time Memory
137542 2019-07-28T06:23:03 Z 김세빈(#3278) Coins (BOI06_coins) C++14
0 / 100
 120 ms 6816 KB 
#include <bits/stdc++.h>

using namespace std;

int C[505050], D[505050];
vector <int> V;
int n, k, s, v;

int main()
{
	int i, r, t;
	
	scanf("%d%d", &n, &k);
	
	for(i=1; i<=n; i++){
		scanf("%d%d", C + i, D + i);
		if(C[i] > k) break;
	}
	
	n = i;
	C[n] = k + 1; D[n] = 1;
	
	V.push_back(0); s = 0;
	
	for(i=1; i<n; i++){
		if(C[i] + C[i] <= C[i + 1]) r = C[i] - 1;
		else r = (C[i + 1] - 1) % C[i];
		if(!D[i] && r >= V[s]){
			V.push_back(V[s] + C[i]); s ++;
		}
	}
	
	printf("%d\n", s);
	
	v = k;
	
	for(i=n-1; i>=1; i--){
		if(k < C[i]) continue;
		
		r = k % C[i];
		t = upper_bound(V.begin(), V.end(), r) - V.begin() - 1;
		if(t + !D[i] == s){
			v -= k - r; k = r; s = t;
			continue;
		}
		
		if(C[i] + C[i] <= r){
			r = C[i] - 1;
			t = upper_bound(V.begin(), V.end(), r) - V.begin() - 1;
			if(t + !D[i] == s){
				v -= k - k % C[i] - C[i];
				k = r; s = t;
				continue;
			}
		}
		
		k = C[i] - 1;
	}
	
	printf("%d\n", v);
	
	return 0;
}

Compilation message

coins.cpp: In function 'int main()':
coins.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~
coins.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", C + i, D + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Incorrect 2 ms 256 KB Output isn't correct
6 Incorrect 2 ms 256 KB Output isn't correct
7 Incorrect 108 ms 6648 KB Output isn't correct
8 Incorrect 107 ms 6648 KB Output isn't correct
9 Incorrect 120 ms 6648 KB Output isn't correct
10 Incorrect 120 ms 6816 KB Output isn't correct