Submission #1202464

#TimeUsernameProblemLanguageResultExecution timeMemory
1202464Faisal_SaqibSplit the sequence (APIO14_sequence)C++20
0 / 100
0 ms324 KiB
/* VENI VIDI VICI */ // #pragma GCC optimize("Ofast","unroll-all-loops","fast-math","no-stack-protector","give-no-fuck") #include <bits/stdc++.h> // #include <iostream> // #include <vector> // #include <algorithm> // #include <set> // #include <map> using namespace std; #define fi first #define se second #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define rep(i,x, n) for (int i = (x); i < (n); ++i) #define repr(i,x, n) for (int i = (n) - 1; i >= (x); --i) // #define sum accumulate //using i128 = __int128; using ll = long long; using ull = unsigned long long; using ld = long double; using str = string; using pi = pair<int, int>; using pl = pair<ll, ll>; using vi = vector<int>; using vl = vector<ll>; using vpi = vector<pair<int, int>>; using vvi = vector<vi>; using sll = set<ll>; template<class T> istream& operator>>(istream& is, vector<T>& v) { for(auto &i:v) is>>i; return is; } template<class T1,class T2> istream& operator>>(istream& is, pair<T1,T2>& p) { is>>p.fi>>p.se; return is; } template<class T> ostream& operator<<(ostream& os, const vector<T>& v) { for(const auto &i:v) os<<i<<' '; return os; } template<class T1,class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& p) { os<<p.fi<<' '<<p.se; return os; } void pyn(bool x) { cout<<(x?"YES":"NO")<<endl; } void pYN(bool x) { cout<<(x?"Yes":"No")<<endl; } void pAB(bool x) { cout<<(x?"Alice":"Bob")<<endl; } ll powmod(ll a,ll b,ll modulo) { if(b==0){ return 1; } ll temp=powmod(a,b/2,modulo); if(b%2==0){ return (temp*temp)%modulo; } else{ return (a*((temp*temp)%modulo))%modulo; } } bool Prime(ll n){ for (ll i = 2; i*i <= n; i++) if (n % i == 0) return false; return (n>1); } struct line { ld m,c; int ind; line(ld x,ld y,int opt) { m=x; c=y; ind=opt; } pair<ld,int> get(ld x) { return {m*x+c,ind}; } ld inter(const line&b) { return (b.c-c)/(m-b.m); } }; const ll N=1e5+1,K=202,inf=1e18; ll n,k; ll a[N],pre[N]; ll dp[K][N]; int bk[K][N]; deque<line> dsa; void insert(ld x,ld y,int opt) { line cur(x,y,opt); int sz=dsa.size(); while(dsa.size()>=2 and dsa[sz-2].inter(dsa[sz-1])>=dsa[sz-2].inter(cur)) { dsa.pop_back(); sz--; } dsa.pb(cur); } pair<ld,int> getans(ld v) // queries are increasing so just pop front { int s=0,e=dsa.size(); // while(dsa.size()>=2 and dsa[0].inter(dsa[1])<v) // { // dsa.pop_front(); // } // return dsa[0].get(v); while(s+1<e) { int mid=(s+e)/2; if(dsa[mid-1].inter(dsa[mid])>v) { e=mid; } else { s=mid; } } return dsa[s].get(v); } void solve() { cin>>n>>k; k++; for(int i=1;i<=n;i++) { cin>>a[i]; pre[i]=pre[i-1]+a[i]; } for(int i=0;i<=k;i++) { for(int j=0;j<=n;j++) { dp[i][j]=-inf; // if(i==0)dp[i][j]=0; } } dp[0][0]=0; for(int i=1;i<=k;i++) { for(int j=0;j<1;j++) insert(pre[j],-pre[j]*pre[n]+dp[i-1][j],j); for(int j=1;j<=n;j++) { auto tp=getans(pre[j]); // cout<<"MX for "<<j<<' '<<tp.first<<' '<<tp.second<<' '<<" addition "<<pre[j]*(pre[n]-pre[j])<<endl; dp[i][j]=tp.first +pre[j]*(pre[n]-pre[j]); bk[i][j]=tp.second; insert(pre[j],-pre[j]*pre[n]+dp[i-1][j],j); } } cout<<dp[k][n]<<endl; int lp=n; vector<int> ans; for(int p=k;bk[p][lp]>0;p--) { ans.pb(bk[p][lp]); lp=bk[p][lp]; } reverse(all(ans)); cout<<ans<<endl; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int uwu=1; // cin>>uwu; while(uwu--) { solve(); } 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...