Submission #1351427

#TimeUsernameProblemLanguageResultExecution timeMemory
1351427trigonBouquet (EGOI24_bouquet)C++20
0 / 100
18 ms16096 KiB
#include<bits/stdc++.h>
using namespace std;
int solve(int i,int j,vector<vector<int>> &dp,vector<int> &l,vector<int> &r){
    if(i==0) return dp[i][j]=1;
    if(i<0) return 0;
    if(j!=-1 && dp[i][j]!=-1) return dp[i][j];
    //Take
    if(r[i] >= j && j!=-1) return dp[i][j] = solve(i-1,j+1,dp,l,r);
    int option1 = 1 + solve(i-l[i]-1,min(l[i]+1,3),dp,l,r);
    //NotTake
    int option2 = solve(i-1,min(3,j+1),dp,l,r);
    return dp[i][j] = max(option1,option2);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<int> l(n);
    vector<int> r(n);
    int ans=0;
    vector<vector<int>> dp(n,vector<int> (10,-1));
    for(int i=0;i<n;i++){
        cin >> l[i] >> r[i];
    }
    for(int i=0;i<n;i++){
        ans = max(ans,solve(i,-1,dp,l,r));
    }

    cout<<ans<<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...