oj.uz

Submission #137569

# Submission time Handle Problem Language Result Execution time Memory
137569 2019-07-28T06:38:59 Z 구재현(#3286) Coins (BOI06_coins) C++14
0 / 100
 232 ms 82752 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 500005;
const int mod = 1e9 + 7;

int n, k;
int dp[MAXN][40];
int trk[MAXN][40];
pi a[MAXN];

int main(){
	scanf("%d %d",&n,&k);
	for(int i=0; i<n; i++) scanf("%d %d",&a[i].first,&a[i].second);
	dp[n][0] = k + 1;
	for(int i=n-1; i>=0; i--){
		if(a[i].second == 0){
			for(int j=0; j<40; j++){
				dp[i][j] = dp[i + 1][j];
				if(j){
					if(dp[i][j] < dp[i + 1][j - 1] - a[i].first){
						dp[i][j] = dp[i + 1][j - 1] - a[i].first;
						trk[i][j] = 1;
					}
				}
				dp[i][j] = min(dp[i][j], a[i].first);
			}
		}
		else{
			for(int j=0; j<40; j++) dp[i][j] = min(dp[i+1][j], a[i].first);
		}
	}
	int p = 0;
	while(dp[0][p + 1]) p++;
	cout << p << endl;
	int curVal = 1;
	for(int i=0; i<n; i++){
		if(a[i].second == 0){
			if(trk[i][p]){
				curVal = dp[i + 1][p - 1];
				p--;
			}
		}
	}
	cout << k + 1 - curVal << endl;
}

Compilation message

coins.cpp: In function 'int main()':
coins.cpp:14: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:15:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<n; i++) scanf("%d %d",&a[i].first,&a[i].second);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 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 380 KB Output isn't correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Incorrect 226 ms 82680 KB Output isn't correct
8 Incorrect 186 ms 82528 KB Output isn't correct
9 Incorrect 232 ms 82752 KB Output isn't correct
10 Incorrect 232 ms 82680 KB Output isn't correct