oj.uz

Submission #139802

# Submission time Handle Problem Language Result Execution time Memory
139802 2019-08-01T12:30:59 Z gs14004 Coins (BOI06_coins) C++17
10 / 100
 245 ms 88516 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 += a[i].first;
				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
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Correct 2 ms 376 KB Output is 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 376 KB Output isn't correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Incorrect 225 ms 88440 KB Output isn't correct
8 Incorrect 193 ms 88312 KB Output isn't correct
9 Incorrect 237 ms 88516 KB Output isn't correct
10 Incorrect 245 ms 88120 KB Output isn't correct