Submission #1165477

#TimeUsernameProblemLanguageResultExecution timeMemory
1165477Tony1234Bouquet (EGOI24_bouquet)C++20
0 / 100
3095 ms2828 KiB
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#ifdef _debug 
#include </home/tony/templates/debug.cpp>
#else
#define debug(...) 42
#endif

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define vi vector<int>
#define vt vector
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int MOD = 1e9 + 7, inf = (int)2e9;
const ll infll = (ll)1e18;

void solve(){
    int N; cin >> N;
    vector<int> dp(N+1); //dp[i] -> answer is i choose i as the last tulip

    vector<int> l(N+1), r(N+1);
    for(int i = 1; i <= N; i++)cin >> l[i] >> r[i];
    for(int i = 1; i <= N; i++){
        dp[i] = 1; 
        for(int j = 1; j < i; j++){
            if(j + r[j] < i && i - l[i] > j){
                dp[i] = max(dp[i], dp[j+1]+1);
            }
        }
    }
    cout << *max_element(all(dp)) << '\n';
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    solve();
}




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