Submission #740641

#	Time	Username	Problem	Language	Result	Execution time	Memory
740641		abczz	Split the sequence (APIO14_sequence)	C++14	100 / 100	832 ms	82592 KiB

sequence

#include <iostream>
#include <vector>
#include <cstring>
#include <deque>
#include <algorithm>
#define ll long long

using namespace std;

struct line{
  ll m;
  ll c;
  ll id;
};

long double I, J;

long double intx(line X, line Y) {
  return (long double)(X.c-Y.c)/(Y.m-X.m);
}

line cur, u, v;
bool B;
deque <line> dq;
vector <ll> V;
int P[200][100000];
ll n, k, t, f = -1, dp[2][100000], ps[100000];
int main() {
  memset(P, -1, sizeof P);
  cin >> n >> k;
  for (int i=0; i<n; ++i) {
    cin >> t;
    if (i == 0) ps[i] = t;
    else ps[i] = ps[i-1] + t;
  }
  for (int i=0; i<n-1; ++i) {
    dp[1][i] = ps[i] * (ps[n-1]-ps[i]);
    //cout << dp[0][i] << " ";
  }
  //cout << endl;
  for (int i=1; i<k; ++i) {
    dq.clear();
    swap(dp[0], dp[1]);
    dq.push_back({ps[i-1], dp[0][i-1], i-1});
    for (int j=i; j<n-1; ++j) {
      while (dq.size() >= 2) {
        u = dq.front();
        dq.pop_front();
        v = dq.front();
        if (u.m*(ps[j]-ps[n-1])+u.c > v.m*(ps[j]-ps[n-1])+v.c) {
          dq.push_front(u);
          break;
        }
      }
      u = dq.front();
      P[i][j] = u.id;
      dp[1][j] = u.m*(ps[j]-ps[n-1])+u.c+ps[n-1]*ps[j]-ps[j]*ps[j];
      u = dq.back();
      cur = {ps[j], dp[0][j], j};
      B = true;
      while (!dq.empty()) {
        u = dq.back();
        if (u.m == cur.m) {
          if (u.c > cur.c) {
            B = false;
            break;
          }
          dq.pop_back();
        }
        else break;
      }
      if (!B) continue;
      while (dq.size() >= 2) {
        u = dq.back();
        dq.pop_back();
        v = dq.back();
        I = intx(v, u);
        J = intx(v, cur);
        if (I < J) {
          dq.push_back(u);
          break;
        }
      }
      dq.push_back(cur);
    }
    //cout << endl;
  }
  int j;
  for (int i=k-1; i<n-1; ++i) {
    if (dp[1][i] > f) {
        f = dp[1][i], j = i;
    }
  }
  cout << f << '\n';
  for (int i=k-1; i>=0; --i) {
    V.push_back(j+1);
    j = P[i][j];
  }
  reverse(V.begin(), V.end());
  for (auto u : V) {
    cout << u << " ";
  }
  cout << '\n';
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:96:18: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |     V.push_back(j+1);
      |                 ~^~

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