Submission #252633

#	Time	Username	Problem	Language	Result	Execution time	Memory
252633		ChrisT	Split the sequence (APIO14_sequence)	C++17	100 / 100	401 ms	82676 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define min(...) minn(__VA_ARGS__)
#define max(...) maxx(__VA_ARGS__)
#define stringio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define m first
#define b second
char _;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename t>constexpr const t minn(const t x,const t y){return x<y?x:y;}
template<typename t,typename ...r>constexpr const t minn(const t x,const r ...xs){return minn(x,minn(xs...));}
template<typename t>constexpr const t maxx(const t x,const t y){return x>y?x:y;}
template<typename t,typename ...r>constexpr const t maxx(const t x,const r ...xs){return maxx(x,maxx(xs...));}
template <typename t> void scan (t& x) {do{while((x=getchar_unlocked())<'0'); for(x-='0'; '0'<=(_=getchar_unlocked()); x=(x<<3)+(x<<1)+_-'0');}while(0);}
template <typename t, typename ...r> void scan (t& x, r&... xs) {scan(x); scan(xs...);}
const int MAXN = 1e5+2, MAXK = 202;
ll dp[MAXN], psa[MAXN];
int par[MAXK][MAXN], which[MAXN];
pll lines[MAXN];
ll val (pll line, ll x) {return line.m * x + line.b;}
double intersect (pll f, pll s) {
  ll i = f.b - s.b, j = s.m - f.m;
  if (j < 0) j = -j, i = -i;
  if (j == 0) return 1e18;
  return (double)i/j;
}
int main() {
    int n,K,l,r;
    scan(n,K);
    for (int i = 1; i <= n; i++) scan(psa[i]), psa[i] += psa[i-1];
    lines[0] = {0,0}; which[0] = 0;
    for (int k = 1; k <= K; k++) {
      l = 0, r = 1;
      for (int i = 1; i <= n; i++) {
          while (r-l>1 && val(lines[l],psa[i]) <= val(lines[l+1],psa[i])) l++;
          pll nline = {psa[i],dp[i] - psa[i] * psa[i]};
          dp[i] = val(lines[l],psa[i]);
          par[k][i] = which[l];
          while (r-l>1 && intersect(nline,lines[r-1]) < intersect(lines[r-1],lines[r-2])) r--;
          which[r] = i, lines[r++] = nline;
      }
    }
    printf ("%lld\n",dp[n]);
    int cur = n;
    while (K) {
      printf ("%d%c",par[K][cur]," \n"[K==1]);
      cur = par[K--][cur];
    }
    return 0;
}

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