Submission #989670

#	Time	Username	Problem	Language	Result	Execution time	Memory
989670		fimh	Split the sequence (APIO14_sequence)	C++17	49 / 100	66 ms	131072 KiB

sequence

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

int n, k, best, cost;
int a[N], ps[N], dp[N][K], trace[N][K];

void compute(int j, int l, int r, int optl, int optr){
     if (l > r) return;
     int 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][j - 1] + cost){
               best = dp[i - 1][j - 1] + cost;
               trace[mid][j] = i;
          }
     }
     dp[mid][j] = best;
     int 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 >> a[i];
          ps[i] = ps[i - 1] + a[i];
     }
     for (int i = 1; i <= n; ++i){
          dp[i][1] = sq(ps[i]);
     }
     for (int j = 2; j <= k + 1; ++j){
          compute(j, 1, n, 1, n);
     }
     int ans = (sq(ps[n]) - dp[n][k + 1]) >> 1;
     // cout << dp[n][k + 1] << " ";
     cout << ans << "\n";
     vector<int> path;
     // for (int i = 1; i <= n; ++i){
     //      for (int j = 1; j <= k + 1; ++j){
     //           cout << trace[i][j] << " \n"[j == k + 1];
     //      }
     // }
     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: 0 / 11
• Subtask 2: 11 / 11
• Subtask 3: 0 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29