Submission #111131

#	Time	Username	Problem	Language	Result	Execution time	Memory
111131		aleksami	Split the sequence (APIO14_sequence)	C++14	11 / 100	30 ms	2788 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
#define MAXN 200005
#define MAXK 205
typedef long long ll;
ll a[MAXN];
ll opt[MAXN][MAXK];
ll dp[MAXN][MAXK];
const ll INF = 1e18;
struct line {ll k;ll n;int id;};

deque <line> q;
double presekx(line x,line y) {
    if(x.k==y.k) return -1e18;
    return 1.0*(x.n-y.n)/(y.k-x.k);
}
line next_front()
{
  line x = q.front();
  q.pop_front();
  line y = q.front();
  q.push_front(x);
  return y;
}
line prev_back()
{
  line x = q.back();
  q.pop_back();
  line y = q.back();
  q.push_back(x);
  return y;
}
int main() 
{
    ios_base::sync_with_stdio(false);
    int n,k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
    {
      	cin >> a[i];
      	a[i]+=a[i-1];
    }
    for(int j = 1; j <= k ;j++) 
    {
      	q.clear();
        for(int i = 1; i <= n; i++) 
        {
            while(q.size() >= 2 && presekx(q.front(),next_front()) <= a[i])q.pop_front();
            if(q.size())
            {
              dp[j][i]=q.front().k*a[i]+q.front().n;
              opt[j][i]=q.front().id;
            }
          	line now;
          	now.k=a[i];
          	now.n=dp[j-1][i]-a[i]*a[i];
          	now.id=i;
            while(q.size() >= 2 && presekx(prev_back(),q.back()) >= presekx(q.front(),now))q.pop_back();
          	q.push_back(now);
        }
    }
    cout << dp[k][n] << "\n";
  	int now = n;
    while(k > 0)
    {
      cout << opt[k][now] << " ";
      now=opt[k][now];
      k--;
    }
    return 0;
}

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