Submission #139802

#	Time	Username	Problem	Language	Result	Execution time	Memory
139802		gs14004	Coins (BOI06_coins)	C++17	10 / 100	245 ms	88516 KiB

coins

#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 (stderr)

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 / 100