제출 #1344772

#제출 시각아이디문제언어결과실행 시간메모리
1344772walizamaneeBouquet (EGOI24_bouquet)C++20
100 / 100
27 ms13700 KiB
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int boro = 200005;
ll vag = 1000000007;

int n , l[boro] , r[boro] , ans[boro] , curans , curpos , uttor;
vector<int> notun[boro];

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

    
    curans = 0;
    curpos = -10000000;
    uttor = 0;
    cin >> n;

    for( int z = 0; z <= n + 1; z++ ){
        notun[z].clear();
    }

    for( int z = 1; z <= n; z++ ){
        cin >> l[z] >> r[z];

        for( auto it : notun[z] ){
            if( ans[it] > curans ){
                curans = ans[it];
                curpos = it;
            }
            else if( ans[it] == curans && it < curpos ){
                curpos = it;
            }
        }

        if( z - l[z] > curpos ){
            ans[z] = curans + 1;
            notun[min( (n + 1) , z + r[z] + 1)].push_back(z);
            uttor = max( uttor , ans[z] );
        } 

    }

    cout << uttor << "\n";

    return 0;
}
#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...