Submission #54262

#	Time	Username	Problem	Language	Result	Execution time	Memory
54262		nimar	Split the sequence (APIO14_sequence)	C++11	0 / 100	2055 ms	86328 KiB

sequence

#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <utility>
#include <algorithm>
#include <list>
#include <limits>
#include <cassert>

typedef long long ll;
static std::vector<int> A;
static std::vector<long long> psum;
static int n, k;
static std::vector<std::vector<int>> offset; // (k+1) x (n+1) -> offset
static std::list<int> answer;

// assume a1 <= a2. Want smallest x(>=0) s.t. a2.x + b2 > a1.x + b1
ll intersect(ll a1, ll b1, ll a2, ll b2) {
  if (a1 != a2)
    return (b1 - b2) / (a2 - a1);

  if (b1 > b2)
    return std::numeric_limits<ll>::max();

  return 0LL;
}

static long long dp(void) {
  int k1;
  for (k1=0; k1<=k; k1++)
    offset.push_back(std::vector<int> (n+1, 0));

  std::vector<long long> prevrow(n+1, 0);
  std::vector<long long> row(n+1, 0);

  // k = 0 => all offsets are zero
  for (k1=1; k1<=k; k1++) {
    std::swap(row, prevrow);

    for (int i=2; i<=k1; i++)
      row[i] = 0LL;

    row[k1+1] = prevrow[k1] + psum[k1] * A[k1];
    offset[k1][k1+1] = k1;


    std::vector<ll> slopes;
    std::vector<ll> intercepts;
    std::vector<int> indices;
    std::vector<ll> xmins;

    slopes.push_back(psum[k1]);
    intercepts.push_back(- psum[k1] * psum[k1] + prevrow[k1]);
    indices.push_back(k1);
    xmins.push_back(0);

    for (int i=(k1+2); i<=n; i++) {
      // find j to maximize: prevrow[j] + psum[j] * (psum[i] - psum[j]);
      // j goes from k1 to i-1

      ll slope = psum[i-1];
      ll intercept = -psum[i-1] * psum[i-1] + prevrow[i-1];

      while (true) {
        ll x = intersect(slopes.back(), intercepts.back(), slope, intercept);
        if (x <= xmins.back()) {
          slopes.pop_back();
          intercepts.pop_back();
          indices.pop_back();
          xmins.pop_back();

          if (!slopes.empty())
            continue;
        }
        slopes.push_back(slope);
        intercepts.push_back(intercept);
        indices.push_back(i-1);
        xmins.push_back(x);
        break;
      }
      auto itr = upper_bound(xmins.begin(), xmins.end(), psum[i]);
      --itr;
      assert(*itr <= psum[i]);
      int j = indices[itr - xmins.begin()];

      row[i] = prevrow[j] + psum[j] * (psum[i] - psum[j]);
      offset[k1][i] = j;
    }

    /*
    std::cout << "k " << k1 << " val ";
    for (long long x: row)
      std::cout << x << " ";
    std::cout << std::endl;
    std::cout << "k " << k1 << " off ";
    for (long x: offset[k1])
      std::cout << x << " ";
    std::cout << std::endl;
    */
  }

  int lastoffset = n;
  k1 = k;
  while (k1 > 0) {
    lastoffset = offset[k1][lastoffset];
    answer.push_front(lastoffset);
    k1 --;
  }

  return row[n];
}

int main(int argc, char const *argv[]) {
  std::cin >> n >> k;
  for (int i=0; i<n; i++) {
    int a;
    std::cin >> a;
    A.push_back(a);
  }
  psum.push_back(0);
  for (int i=0; i<n; i++)
    psum.push_back(A[i] + psum[i]);

  std::cout << dp() << std::endl;
  for (int a: answer)
    std::cout << a << " ";
  std::cout << std::endl;

  return 0;
}

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