Submission #898671

#	Time	Username	Problem	Language	Result	Execution time	Memory
898671		NeroZein	Split the sequence (APIO14_sequence)	C++17	50 / 100	2025 ms	131072 KiB

sequence

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int K = 202;
const int N = 1e5 + 5;

struct Line {
  int m, b;
  Line() {}
  Line(int m_, int b_) : m(m_), b(b_) {}
  long long val(int x) {
    return (long long) m * x + b;
  }
};

int a[N];
int path[N][K];
long long dp[N][K];
int pref[N], suf[N];
Line seg[N * 15]; 
int idd, lx[N * 15], rx[N * 15];

//void upd(int& nd, int l, int 

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; ++i) {
    pref[i] = pref[i - 1] + a[i];
  }
  for (int i = n; i >= 1; --i) {
    suf[i] = suf[i + 1] + a[i];
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= k; ++j) {
      dp[i][j] = -1e18;
    }
  }
  dp[0][k] = 0; 
  int ind = 0; 
  long long ans = -LLONG_MAX; 
  for (int j = k - 1; j >= 0; --j) {
    for (int i = 1; i < n; ++i) {
      long long c = (long long) suf[i + 1] * pref[i];
      for (int l = i - 1; l >= 0; --l) {
        long long cl = dp[l][j + 1] - (long long) suf[i + 1] * pref[l];
        if (c + cl > dp[i][j]) {
          dp[i][j] = c + cl;
          path[i][j] = l;
        }
        dp[i][j] = max(dp[i][j], c + cl);
        if (j == 0 && dp[i][j] > ans) {
          ans = dp[i][j];
          ind = i;
        }
      }
    }
  }
  int cnt = 0;
  vector<int> p;
  while (ind) {
    p.push_back(ind);
    ind = path[ind][cnt++];
  }
  reverse(p.begin(), p.end()); 
  cout << ans << '\n'; 
  for (int i : p) {
    cout << i << ' ';
  }
  return 0;
}

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