Submission #1362434

#TimeUsernameProblemLanguageResultExecution timeMemory
1362434avahwBouquet (EGOI24_bouquet)C++20
8 / 100
17 ms1860 KiB
#include <bits/stdc++.h>
using namespace std;

int n;
map<pair<int, int>, int> memo;

int solve(int i, int last_picked_ind, vector<pair<int, int>>& ranges){
    // check if we can pick this one
    if(i >= n) return 0;
    int l = ranges[i].first; int r = ranges[i].second;
    if(memo.find({i, last_picked_ind}) != memo.end()) return memo[{i, last_picked_ind}];
    if(last_picked_ind >= i - l) return solve(i + 1, last_picked_ind, ranges);
    // pick or dont pick
    int pick = 1 + solve(i + r + 1, i, ranges);
    int dont = solve(i + 1, last_picked_ind, ranges);
    memo[{i, last_picked_ind}] = max(pick, dont);
    return max(pick, dont);
}

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;
    }
    int l = tulips[0].first;
    cout << (n / (l + 1 )) + min(1, n % (l + 1)) << "\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...