Submission #870243

#	Time	Username	Problem	Language	Result	Execution time	Memory
870243		Matjaz	Coins (BOI06_coins)	C++14	100 / 100	623 ms	91660 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;
map<int,int> nextc;


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){
        nextc[max_sum] = -i;
        return dp[max_sum] = best(c[i] - 1);
    }
    
    int a = best(c[i] - 1);
    int b = 1 + best(min(c[i] - 1, max_sum - c[i]));
    if (b > a){
        nextc[max_sum] = i;
    } else nextc[max_sum] = -i;
    
    return dp[max_sum] = max(a,b);
}
                    
                    
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;
    int total = 0;
    int max_sum = K - 1;
    while (max_sum > 0){
        int i = nextc[max_sum];
        if (i >= 0){
            //cout << c[i] << endl;
            total += c[i];
            max_sum = min(c[i] - 1, max_sum - c[i]);
        } else {
            max_sum = c[-i] - 1;
        }
    }
    
    cout << K - total << endl;
    return 0;
}

• Subtask 1: 100 / 100