oj.uz

Submission #870243

# Submission time Handle Problem Language Result Execution time Memory
870243 2023-11-07T10:47:03 Z Matjaz Coins (BOI06_coins) C++14
100 / 100
 623 ms 91660 KB 

#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 408 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 623 ms 90648 KB Output is correct
8 Correct 543 ms 90452 KB Output is correct
9 Correct 603 ms 91352 KB Output is correct
10 Correct 586 ms 91660 KB Output is correct