Submission #111031

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

sequence

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
struct lajn
{
  ll k;
  ll n;
  int idx;
};
#define MAXN 100005
#define MAXK 205
deque <lajn> q;
ll a[MAXN];
ll dp[MAXN][MAXK];
int opt[MAXN][MAXK];

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

bool useless(ll x)
{
  lajn a = q.front();
  q.pop_front();
  lajn b = q.front();
  q.push_front(a);
  if(f(a.k,a.n,x)<=f(b.k,b.n,x))return true;
  return false;
}

void calc(int idx,int n)
{
  q.clear();
  for(int i = 1; i <= n; i++)
  {
    while(1)
    {
      if(q.size()<=1)break;
      if(useless(a[i]))q.pop_front();
      else break;
    }
    lajn aa = (q.size() > 0) ? q.front():lajn();
    dp[idx][i]=f(aa.k,aa.n,a[i]);
    opt[idx][i]=aa.idx;
    aa.k=a[i];
    aa.n=-a[i]*a[i]+dp[idx-1][i];
    aa.idx=i;
    q.push_back(aa);
  }
}

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 >> a[i];
    a[i]+=a[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