Submission #870242

#	Time	Username	Problem	Language	Result	Execution time	Memory
870242		Matjaz	Coins (BOI06_coins)	C++14	0 / 100	461 ms	73536 KiB

coins

#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <map>

using namespace std;

int N,K;
vector<int> c, d;
map<int,int> dp;


int best(int max_sum){
    
    if (dp.count(max_sum) > 0) return dp[max_sum];
    
    //assert(max_sum >= 0);
    
    //cout << max_sum << endl;
    
    if (max_sum == 0) return 0;
    
    int i = (upper_bound(c.begin(), c.end(), max_sum) - c.begin()) - 1;
    if (d[i] == 1) return dp[max_sum] = best(c[i] - 1);
    
    return dp[max_sum] = max(best(c[i] - 1), 1 + best(min(c[i] - 1, max_sum - c[i])));
}
                    
                    
int main(){
    cin >> N >> K;
    c.assign(N, 0);
    d.assign(N, 0);
    for (int i=0;i<N;i++) cin >> c[i] >> d[i];
    
    cout << best(K-1) << endl;
    cout << -1 << endl;
    return 0;
}

• Subtask 1: 0 / 100