Submission #111122

#	Time	Username	Problem	Language	Result	Execution time	Memory
111122		aleksami	Split the sequence (APIO14_sequence)	C++14	33 / 100	121 ms	2472 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
#define MAXN 100005
#define MAXK 205
typedef long long ll;
ll dp[MAXN][MAXK];
ll s[MAXN];
int opt[MAXN][MAXK];

struct lajn 
{
  ll k;
  ll n;
  int idx;
};

ll f(lajn a,ll x)
{
  return a.k*x+a.n;
}

bool bad(lajn x,lajn y,lajn z)
{
  return 1LL*(x.n - y.n)*(z.k - y.k) >= 1LL*(y.n - z.n)*(y.k - x.k);
}

lajn prev_back(deque <lajn> q)
{
  lajn x = q.back();
  q.pop_back();
  lajn y = q.back();
  q.push_back(x);
  return y;
}

void calc(int idx,int n)
{
  deque <lajn> q;
  for(int i = idx; i <= n; i++)
  {
    while(1)
    {
      if(q.size()<=1)break;
      lajn a=q.front();
      q.pop_front();
      lajn b=q.front();
      if(f(a,s[i])<=f(b,s[i]))continue;
      q.push_front(a);
      break;
    }
    if(q.size())
    {
      dp[idx][i]=f(q.front(),s[i]);
      opt[idx][i]=q.front().idx;
    }
    lajn a;
    a.k=s[i];
    a.n=-s[i]*s[i]+dp[idx-1][i];
    a.idx=i;
    while(q.size()>1 && bad(prev_back(q),q.back(),a))q.pop_back();
    while(q.size() && a.k==q.front().k && a.n>q.front().n)q.pop_back();
    q.push_back(a);
  }
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n,k;
  cin >> n >> k;
  for(int i = 1; i <= n; i++)
  {
    cin >> s[i];
    s[i]+=s[i-1];
  }
  for(int i = 1; i <= k; i++)
  {
    calc(i,n);
  }
  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: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29