제출 #530646

#제출 시각아이디문제언어결과실행 시간메모리
530646huangqrFinancial Report (JOI21_financial)C++14
48 / 100
4064 ms12780 KiB
#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<ld,ld> pd; typedef pair<ll,ll> pl; typedef pair<ll,pl> ppl; const ll lim=3e5+5,mod=1e9+7; ll par[lim],a[lim],dp[lim]; //Calced vals can be updated later. In a strict DP sense it would be dp(pos, time) rather than just dp(pos) ll fs(ll x){ if(x==par[x])return x; else return par[x]=fs(par[x]); } void mergeset(ll a,ll b){ a=fs(a),b=fs(b); if(a==b)return; par[a]=b; } int main(){ ios_base::sync_with_stdio(0);cin.tie(0); ll n,d; cin>>n>>d; vector<pl>v; for(int i=0;i<n;i++){ cin>>a[i]; par[i]=i; v.emplace_back(a[i],-i); } sort(v.begin(),v.end()); for(auto p:v){ ll i=-p.second; dp[i]=max(1ll,dp[i]); for(int j=max(i-d,0ll);j<i;j++)dp[i]=max(dp[i],dp[j]+1); ll t = fs(i); //t is the rightmost node to which we can push a dp-val update while(t < min(i+d,n-1)){ mergeset(t, t+1); t = fs(t); } for(int j=i+1;j<=t;j++){ if(dp[j])dp[j]=max(dp[j],dp[i]); } //cout<<"after "<<i<<" (val "<<p.first<<"):\n"; //for(int i=0;i<n;i++)cout<<dp[i]<<" "; //cout<<"\n"; } cout<<dp[n-1]; 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...