Submission #881758

#TimeUsernameProblemLanguageResultExecution timeMemory
881758androStove (JOI18_stove)C++14
50 / 100
1006 ms7640 KiB
#include <bits/stdc++.h> #define int long long using namespace std; signed main(){ ios::sync_with_stdio(false); cin.tie(0); int n,k; cin>>n>>k; int a[n+1]; for(int i=1;i<=n;i++)cin>>a[i]; int A[n+1]; for(int i=0;i<=n;i++)A[i]=0; A[n]=1; int ans=0; ans+=a[n]+1-a[1]; k--; while(k--){ vector<pair<int,int>>v; int suf[n+1]; suf[n]=n; for(int i=n-1;i>=1;i--){ if(A[i])suf[i]=i; else suf[i]=suf[i+1]; } int pret=1; for(int i=1;i<=n;i++){ if(A[i]){ pret=i; continue; } int R=ans; int sl=suf[i]; R-=a[sl]+1-a[pret+1]; R+=a[sl]+1-a[i+1]; R+=a[i]+1-a[pret+1]; v.push_back({R,i}); } sort(v.begin(),v.end()); int b=v[0].second; A[b]=1; int sl=-1; for(int i=b+1;i<=n;i++){ if(A[i]){ sl=i; break; } } pret=1; for(int i=1;i<b;i++){ if(A[i]){ pret=i; } } ans-=a[sl]+1-a[pret+1]; ans+=a[sl]+1-a[b+1]; ans+=a[b]+1-a[pret+1]; } cout<<ans; } /* a[i]+1-a[pret]; pret=i+1; */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...