Submission #1363223

#TimeUsernameProblemLanguageResultExecution timeMemory
1363223avahwBouquet (EGOI24_bouquet)C++20
24 / 100
19 ms15292 KiB
#include <bits/stdc++.h>
using namespace std;

int n;
map<pair<int, int>, int> memo;
int calls = 0;

int solve(int i, vector<int>& dp, vector<pair<int, int>>& ranges){
    if(dp[i] != -1) return dp[i];
    if(i < 0) return 0;
    int pick = 1;
    int dont = solve(i - 1, dp, ranges);
    if(i - ranges[i].first >= 0) pick += solve(i - ranges[i].first - 1, dp, ranges);
    dp[i] = max(pick, dont);
    return dp[i];
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> n;
    vector<pair<int, int>> tulips(n);
    for(int i = 0; i < n; i++){
        cin >> tulips[i].first >> tulips[i].second;
    }
    vector<int> dp(n, -1);
    dp[0] = 1;
    cout << solve(n-1, dp, tulips) << "\n";
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...