Submission #172913

#	Time	Username	Problem	Language	Result	Execution time	Memory
172913		RafaelSus	Split the sequence (APIO14_sequence)	C++14	71 / 100	2073 ms	86160 KiB

sequence

#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;
 
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 pos,ll x){
  return m[pos]*x+b[pos];
}
 
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]};
}
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<<' ';
}
ll dp[2][N];
ll a[N],pref[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];
    pref[i]=pref[i-1]+a[i];
  }
  
  for(int i=1;i<=n;i++){
    dp[1][i]=pref[i]*(pref[n]-pref[i]);
    path[i][1]=0;
  }
  for(int i=2;i<=k;i++){
    int v=(i-1)%2;
    m.clear();
    b.clear();
    idx.clear();
    ptr=0;
    add(0,0,0);
    for(int j=i-1;j<n;j++){
      if(j==i-1){
        add(-pref[j],dp[v][j],j);
        continue;
      }
      pair<ll,int>tmp=get(pref[n]-pref[j]);
      dp[v^1][j]=tmp.first+pref[n]*pref[j]-pref[j]*pref[j];
      path[j][i]=tmp.second;
      add(-pref[j],dp[v][j],j);
    }
  }
  ll mx=0,st=1;
  for(int i=1;i<n;i++){
    if(dp[k%2][i]>mx){
      mx=dp[k%2][i];
      st=i;
    }
  }
  cout<<mx<<'\n';
  print(st,k);
}

Compilation message (stderr)

sequence.cpp: In function 'std::pair<long long int, int> get(ll)':
sequence.cpp:41:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ptr>=m.size())ptr=m.size()-1;
      ~~~^~~~~~~~~~
sequence.cpp:42:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr+1<m.size()&&func(ptr,x)<=func(ptr+1,x))ptr++;
         ~~~~~^~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29