Submission #725131

#	Time	Username	Problem	Language	Result	Execution time	Memory
725131		quiet_space	Split the sequence (APIO14_sequence)	C++14	100 / 100	1381 ms	81372 KiB

sequence

#include <bits/stdc++.h>
#define FOR(i,j,k) for(int i=j; i<=k; ++i)
#define ROF(i,j,k) for(int i=j; i>=k; --i)
inline int read (void) {
  int x = 0, f = 1, ch = getchar();
  while(!isdigit(ch)) { if(ch == '-') f = -f; ch = getchar(); }
  while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
  return x * f;
}
using ll = long long;
const int maxn = 100005;
int a[maxn], G[205][maxn];
ll f[maxn], g[maxn];
void dfs (int k, int n) {
  if(k == 1) return ;
  dfs (k-1, G[k][n]);
  printf("%d ", G[k][n]);
}
inline void solve (int t, int l, int r, int L, int R) {
  if(L == R) {
    FOR(i,l,r) G[t][i] = L, f[i] = g[L] + 1ll * (a[i] - a[L]) * a[L];
    return ;
  }
  int mid = (l + r >> 1), pos = L;
  ll v = g[L] + 1ll * (a[mid] - a[L]) * a[L], tp;
  FOR(i,L+1,R) if((tp = g[i] + 1ll * (a[mid] - a[i]) * a[i]) > v) v = tp, pos = i;
  f[mid] = v, G[t][mid] = pos;
  if(l < mid) solve (t, l, mid-1, L, pos);
  if(mid < r) solve (t, mid+1, r, pos, R);
}
int main (void) {
  int n = read(), k = read() + 1;
  FOR(i,1,n) a[i] = a[i-1] + read();
  std::fill (f, f+n+1, -1ll << 60);
  f[0] = 0;
  FOR(t,1,k) {
    std::swap (f, g);
    solve (t, t, n, t-1, n-1);
  }
  printf("%lld\n", f[n]); dfs (k, n);
  return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'void solve(int, int, int, int, int)':
sequence.cpp:24:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |   int mid = (l + r >> 1), pos = L;
      |              ~~^~~

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