Submission #1193171

#TimeUsernameProblemLanguageResultExecution timeMemory
1193171DobromirAngelovFinancial Report (JOI21_financial)C++20
48 / 100
1993 ms226928 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; const int MAXN=3e5+5; int n,d; int a[MAXN]; set<int> s; map<int,int> code; priority_queue<pair<int,int> > dp[7005]; void compress() { for(int i=1;i<=n;i++) s.insert(a[i]); int i=1; for(auto x: s) { code[x]=i; i++; } for(int i=1;i<=n;i++) a[i]=code[a[i]]; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>d; for(int i=1;i<=n;i++) cin>>a[i]; compress(); //for(int i=0;i<=n;i++) dp[i].push({0,}) for(int i=1;i<=n;i++) { int bst=1; for(int j=1;j<a[i];j++) { while((!dp[j].empty()) && dp[j].top().second<i-d) dp[j].pop(); if(!dp[j].empty()) bst=max(bst, dp[j].top().first+1); } while((!dp[a[i]].empty()) && dp[a[i]].top().second<i-d) dp[a[i]].pop(); if(!dp[a[i]].empty()) bst=max(bst, dp[a[i]].top().first); dp[a[i]].push({bst,i}); for(int j=a[i]+1;j<=n;j++) { while((!dp[j].empty()) && dp[j].top().second<i-d) dp[j].pop(); if(!dp[j].empty()) dp[j].push({dp[j].top().first, i}); } } int ans=0; for(int i=1;i<=n;i++) { while(!dp[i].empty()) { if(dp[i].top().second==n) ans=max(ans, dp[i].top().first); dp[i].pop(); } } cout<<ans<<endl; 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...
#Verdict Execution timeMemoryGrader output
Fetching results...