Submission #740635

#	Time	Username	Problem	Language	Result	Execution time	Memory
740635		abczz	Split the sequence (APIO14_sequence)	C++14	0 / 100	22 ms	3292 KiB

sequence

#include <iostream>
#include <deque>
#define ll long long

using namespace std;

struct line{
  ll m;
  ll c;
};

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;
ll n, k, t, f = -1, dp[2][100000], ps[100000];
int main() {
  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]});
    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();
      dp[1][j] = u.m*(ps[j]-ps[n-1])+u.c+ps[n-1]*ps[j]-ps[j]*ps[j];
      //cout << u.m << "*" << ps[j-1] << "+" << u.c << endl;
      //cout << dp[i][j] << endl;
      u = dq.back();
      cur = {ps[j], dp[0][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;
  }
  for (int i=k-1; i<n-1; ++i) {
    f = max(f, dp[1][i]);
  }
  cout << f << '\n';
}

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