제출 #1351420

#제출 시각아이디문제언어결과실행 시간메모리
1351420trigonBouquet (EGOI24_bouquet)C++20
28 / 100
3098 ms2628 KiB
#include<bits/stdc++.h>
using namespace std;
int solve(int i,vector<int> &dp,vector<int> &l,vector<int> &r){
    if(i==0) return dp[i]=1;
    if(i<0) return 0;
    if(dp[i]!=-1) return dp[i];
    int ans = 0;
    for(int j=i-l[i]-1;j>=0;j--){
        if(j + r[j] < i) ans=max(ans,solve(j,dp,l,r));
    }
    return dp[i] = 1 + ans;
}
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<int> dp(n,-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,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...