Submission #442074

#TimeUsernameProblemLanguageResultExecution timeMemory
442074EvirirFeast (NOI19_feast)C++17
30 / 100
244 ms19764 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; #define watch(x) cout<<(#x)<<"="<<(x)<<'\n' #define mset(d,val) memset(d,val,sizeof(d)) #define setp(x) cout<<fixed<<setprecision(x) #define forn(i,a,b) for(int i=(a);i<(b);i++) #define fore(i,a,b) for(int i=(a);i<=(b);i++) #define pb push_back #define F first #define S second #define pqueue priority_queue #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef pair<ll,ll> ii; typedef pair<ii,ll> iii; typedef vector<ll> vi; typedef vector<ii> vii; typedef long double ld; template<typename T> using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; void amin(ll &a, ll b){ a=min(a,b); } void amax(ll &a, ll b){ a=max(a,b); } void YES(){cout<<"YES\n";} void NO(){cout<<"NO\n";} void SD(int t=0){ cout<<"PASSED "<<t<<endl; } const ll INF = ll(1e18); const int MOD = 998244353; const bool DEBUG = 0; const int MAXN = 300005; int n,K; ll a[MAXN]; ll p[MAXN]; ll dp[MAXN], cnt[MAXN]; iii pre[MAXN]; //best dp[j-1]+sum(j..i) for j<=i ll sum(int l, int r){ return p[r]-(l?p[l-1]:0LL); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>K; fore(i,1,n) { cin>>a[i]; p[i]=p[i-1]+a[i]; } dp[0]=cnt[0]=0; pre[0]={{0,0},0}; ll ans=0; for(ll L=0,R=1e16;L<=R;) { ll mid=(L+R)>>1; fore(i,1,n) { iii tmp=pre[i-1]; tmp.F.F+=a[i]; pre[i]=max({{dp[i-1]+a[i],-cnt[i-1]-1}, i}, tmp); if(pre[i].F.F-mid>dp[i-1]) // strict; use as few as possible { dp[i]=pre[i].F.F-mid; cnt[i]=cnt[pre[i].S]+1; } else { dp[i]=dp[i-1]; cnt[i]=cnt[i-1]; } } if(cnt[n]<=K) { ans=dp[n]+cnt[n]*mid; R=mid-1; } else L=mid+1; if(DEBUG && ans>0) { cout<<"mid="<<mid<<'\n'; cout<<"a: "; fore(i,1,n) cout<<a[i]<<" "; cout<<'\n'; cout<<"dp: "; fore(i,1,n) cout<<dp[i]<<" "; cout<<'\n'; cout<<"cnt: "; fore(i,1,n) cout<<cnt[i]<<" "; cout<<'\n'; cout<<"pre: "; fore(i,1,n) cout<<"("<<pre[i].F.F<<","<<pre[i].F.S<<") "; cout<<'\n'; cout<<"ans: "<<dp[n]+cnt[n]*mid<<"\n\n"; } } cout<<ans<<'\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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...