Submission #172933

#TimeUsernameProblemLanguageResultExecution timeMemory
172933RafaelSusSplit the sequence (APIO14_sequence)C++14
71 / 100
2036 ms86284 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; typedef long long ll; const ll inf=1e15; #define pb push_back const int INF=(0x3f3f3f3f); vector<ll>m,b; vector<int>idx; int ptr; int path[N][205]; void print(int st,int k) { if(path[st][k]==0) { cout<<st<<" "; return; } print(path[st][k],k-1); cout<<st<<" "; } bool bad(int f1,int f2,int f3) { return (b[f3]-b[f1])*(m[f1]-m[f2])>=(b[f2]-b[f1])*(m[f1]-m[f3]); } void add(ll m_,ll b_,int id) { m.push_back(m_); b.push_back(b_); idx.push_back(id); int sz=m.size(); while(sz>=3 && bad(sz-3,sz-2,sz-1)) { m.erase(m.end()-2); b.erase(b.end()-2); idx.erase(idx.end()-2); sz--; } } ll func(int p,ll x) { return m[p]*x+b[p]; } pair<ll,int> get(ll x) { if(ptr>=m.size())ptr=m.size()-1; while(ptr+1<m.size() && func(ptr,x)<=func(ptr+1,x))ptr++; return {func(ptr,x),idx[ptr]}; } ll dp[N][2]; ll a[N],s[N]; int main(){ //ios::sync_with_stdio(false); //cin.tie(0);cout.tie(0); int n,k; cin>>n>>k; for(int i=1;i<=n;i++) { cin>>a[i]; s[i]=s[i-1]+a[i]; } for(int i=1;i<=n;i++) { dp[i][1]=s[i]*(s[n]-s[i]); path[i][1]=0; //add(-s[i],dp[i][1]); } for(int i=2;i<=k;i++) { m.clear(); b.clear(); idx.clear(); int v=(i-1)%2; ptr=0; add(0,0,0); for(int j=1;j<=n;j++) { if(j<i ) { if(j==i-1) add(-s[j],dp[j][v],j); continue; } pair<ll,int> pd=get(s[n]-s[j]); dp[j][v^1]=pd.first+s[n]*s[j]-s[j]*s[j]; path[j][i]=pd.second; add(-s[j],dp[j][v],j); } } ll mx=0,st=1; for(int i=1;i<n;i++) { if(dp[i][k%2]>=mx) { mx=dp[i][k%2]; st=i; } } cout<<mx<<endl; print(st,k); }

Compilation message (stderr)

sequence.cpp: In function 'std::pair<long long int, int> get(ll)':
sequence.cpp:57:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(ptr>=m.size())ptr=m.size()-1;
     ~~~^~~~~~~~~~
sequence.cpp:58:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ptr+1<m.size() && func(ptr,x)<=func(ptr+1,x))ptr++;
        ~~~~~^~~~~~~~~
#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...