oj.uz

Submission #870242

# Submission time Handle Problem Language Result Execution time Memory
870242 2023-11-07T10:15:25 Z Matjaz Coins (BOI06_coins) C++14
0 / 100
 461 ms 73536 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;


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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Incorrect 383 ms 72740 KB Output isn't correct
8 Incorrect 461 ms 72528 KB Output isn't correct
9 Incorrect 416 ms 73536 KB Output isn't correct
10 Incorrect 411 ms 72420 KB Output isn't correct