Submission #989681

#	Time	Username	Problem	Language	Result	Execution time	Memory
989681		fimh	Split the sequence (APIO14_sequence)	C++14	100 / 100	1033 ms	81064 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
     
#define fi first
#define se second
#define ll long long
#define sq(i) (ll)(i)*(i)
     
const int N = 1e5 + 1;
const int K = 201;
const ll oo = 1e18;

int n, k, mid, opt;
int ps[N], trace[N][K];
ll dp[N][2], best, cost;

void compute(int j, int l, int r, int optl, int optr){
     if (l > r) return;
     mid = (l + r) >> 1;
     best = oo;
     for (int i = optl; i <= min(mid, optr); ++i){
          cost = sq(ps[mid] - ps[i - 1]);
          if (best >= dp[i - 1][0] + cost){
               best = dp[i - 1][0] + cost;
               trace[mid][j] = i;
          }
     }
     dp[mid][1] = best;
     opt = trace[mid][j];
     compute(j, l, mid - 1, optl, opt);
     compute(j, mid + 1, r, opt, optr);
}    

void pray(){
     cin >> n >> k;
     for (int i = 1; i <= n; ++i){
          cin >> ps[i];
          ps[i] += ps[i - 1];
     }
     for (int i = 1; i <= n; ++i){
          dp[i][0] = sq(ps[i]);
     }
     for (int j = 2; j <= k + 1; ++j){
          compute(j, 1, n, 1, n);
          for (int i = 1; i <= n; ++i){
               dp[i][0] = dp[i][1];
          }
     }
     ll ans = (sq(ps[n]) - dp[n][1]) >> 1ll;
     cout << ans << "\n";
     vector<int> path;
     int y = k + 1, x = trace[n][y];
     for (; y > 1; --y, x = trace[x - 1][y]){
          path.push_back(x - 1);
     }
     reverse(path.begin(), path.end());
     for (int i : path) cout << i << " ";
}
     
signed main() {
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
     int tests = 1; // cin >> tests;
     while (tests--) pray();
}

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