Submission #335364

#	Time	Username	Problem	Language	Result	Execution time	Memory
335364		vkgainz	Split the sequence (APIO14_sequence)	C++17	71 / 100	635 ms	131076 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
ll s[100001];
ll dp[201][100001];
int par[201][100001];
double slope(int p, int x, int y) { // x > y 
  if(s[x] == s[y])
    return 1e9;
  return (double) (dp[p-1][y] - dp[p-1][x] - s[y] * s[y] + s[x] * s[x]) / (s[x] - s[y]);
}

int main() {
  int n, k; cin >> n >> k;
  s[0] = 0;
  for(int i = 1; i <= n; i++) {
    cin >> s[i];
    s[i] += s[i-1];
  }
  dp[0][0] = -1e15;
  par[0][0] = -1;
  for(int i=1;i<=n;i++) {
    dp[0][i] = 0;
    par[0][i] = -1;
  }
  for(int p=1;p<=k;p++) {
    deque<int> q;
    dp[p][0] = -1e15;
    for(int i=1;i<=n;i++) {
      bool found = false;
      if(i<=p) {
        dp[p][i] = -1e15;
        par[p][i] = -1;
        found = true;
      }
      while(q.size()>1 && slope(p, q[1], q[0])<=s[i])
        q.pop_front();
      if(!found) {
        int j = q.front();
        dp[p][i] = dp[p-1][j]+(s[i]-s[j])*1LL*s[j];
        par[p][i] = j;
      }
      while(q.size()>1&&slope(p, q[q.size()-1], q[q.size()-2])>slope(p, i, q[q.size()-1]))
        q.pop_back();
      if(i>=p)
        q.push_back(i);
    }
  }
  vector<int> ans;
  int curr =n;
  for(int p=k;p>=1;p--) {
    ans.push_back(par[p][curr]);
    curr = par[p][curr];
  }
  cout << dp[k][n] << "\n";
  for(auto &a : ans) cout << a << " ";
}

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