Submission #1166911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166911		tuongll	Split the sequence (APIO14_sequence)	C++20	100 / 100	498 ms	81260 KiB

sequence

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <ctime>
#include <cassert>
#include <set>
#include <stack>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <array>
#include <bitset>
#include <sstream>
#include <unordered_map>
using ll = long long;
#define debug(x) cout << #x << " = " << x << '\n'
#define separator "===============================================\n"
#define all(a) a.begin(), a.end()
#define SZ(a) ((int)(a).size())
using namespace std;
const int mxn = 1e5 + 3;
const ll  mod = 1e9 + 7;
const int inf32 = 2e9;
const ll  inf64 = 4e18;
int n, K;
ll pref[mxn], dp[mxn], new_dp[mxn];
int best[203][mxn];
int dq[mxn], l = 1, r = 1; // [l, r)
ll eval(ll x, int i){
  return pref[i] * x + dp[i];
}
long double intersect(int i, int j){
  return (long double)(dp[i] - dp[j]) / (long double)(pref[j] - pref[i]);
}
void add(int i){
  while(r - l > 0){
    if (pref[dq[r - 1]] == pref[i]){
      if (dp[dq[r - 1]] < dp[i]) return;
      else dq[--r] = 0;
      continue;
    }
    if (r - l > 1 && intersect(i, dq[r - 1]) <= intersect(dq[r - 1], dq[r - 2]))
      dq[--r] = 0;
    else break;
  }
  dq[r++] = i;
}
int get(ll x){
  while(r - l > 1 && eval(x, dq[l]) <= eval(x, dq[l + 1]))
    dq[l++] = 0;
  return dq[l];
}
void solve(){
  cin >> n >> K;
  for (int i = 1; i <= n; ++i){
    cin >> pref[i];
    pref[i] += pref[i - 1];
  }
  // 1 split
  for (int i = 1; i <= n; ++i)
    dp[i] = pref[i] * (pref[n] - pref[i]);
  for (int j = 2; j <= K + 1; ++j){
    fill(new_dp + 1, new_dp + n + 1, -inf64);
    fill(dq + 1, dq + n + 1, 0), l = r = 1;
    add(j - 1);
    for (int i = j; i <= n; ++i){
      best[j][i] = get(pref[i] - pref[n]);
      new_dp[i] = eval(pref[i] - pref[n], best[j][i]) + pref[i] * (pref[n] - pref[i]);
      add(i);
    }
    for (int i = 1; i <= n; ++i)
      dp[i] = new_dp[i];
  }

  cout << dp[n] << '\n';
  for (int i = n, j = K + 1; j > 0; i = best[j][i], --j)
    if (i < n) cout << i << ' ';
}
int main(){
  auto start = chrono::steady_clock::now();
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  if (fopen("read.inp", "r")){
    freopen("read.inp", "r", stdin);
    freopen("write.out", "w", stdout);
  }
  int t = 1;
  // cin >> t;
  while(t--) solve();
  chrono::duration<double> elapsed {chrono::steady_clock::now() - start};
  cerr << "\n>> Runtime: " << elapsed.count() << "s\n";
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:88:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     freopen("read.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:89:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     freopen("write.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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