Submission #1152973

#TimeUsernameProblemLanguageResultExecution timeMemory
1152973asdasdSplit the sequence (APIO14_sequence)C++20
100 / 100
708 ms84720 KiB
//gm --- akezhon #include <bits/stdc++.h> // #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #define pb push_back #define pf push_front #define F first #define S second #define all(v) v.begin(),v.end() #define pii pair<int,int> #define tm (tl+tr)/2 #define TL v+v, tl, tm #define TR v+v+1, tm+1, tr #define DA l <= tl && tr <= r #define NE r < tl || tr < l // #define double long double #define ll long long // #define int long long using namespace std; const int N=1e5+7; const int mod=998244353; const ll inf=2e18; struct line{ ll b, k, l, i; }; vector<line>v; ll xint(line& a, line& b){ if(a.k==b.k)return inf; ll x = (b.b-a.b); ll y = (a.k-b.k); if(x%y==0)return x/y; else return x/y+1; } void add(ll b, ll k, ll i){ line x = {b, k, -inf, i}; while(v.size() && (xint(v.back(), x) <= v.back().l || (v.back().k==x.k && x.b <= v.back().b)))v.pop_back(); if(v.empty()){ v.pb(x); } else{ ll inter = xint(v.back(), x); v.pb(x); v.back().l = inter; } } line get(ll x){ int l=0, r=v.size()-1, ans=0; while(l <= r){ int m = (l+r)/2; if(v[m].l <= x)l=m+1, ans=m; else r=m-1; } return v[ans]; } int n, k; int a[N]; ll p[N]; ll dp[2][100005]; int pe[205][100005]; void AlemAmenov(){ cin >> n >> k; for(int i=1; i <= n; i++){ cin >> a[i]; p[i]=p[i-1]+a[i]; } ll mx=0, pos=0; for(int kk=1; kk <= k; kk++){ v.clear(); for(int i=1; i < n; i++){ add(dp[kk&1^1][i-1] - p[n]*p[i-1], p[i-1], i-1); line x = get(p[i]); dp[kk&1][i] = p[n]*p[i]-p[i]*p[i] + x.b + p[i]*x.k; pe[kk][i] = x.i; } } for(int i=1; i < n; i++){ if(dp[k&1][i] >= mx){ mx = dp[k&1][i]; pos = i; } } cout << mx << '\n'; while(k){ cout << pos << ' '; pos = pe[k--][pos]; } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int RealName=1; // cin >> RealName; // srand(time(0)); while(RealName--) AlemAmenov(); 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...