Submission #54239

#	Time	Username	Problem	Language	Result	Execution time	Memory
54239		nimar	Split the sequence (APIO14_sequence)	C++11	11 / 100	32 ms	8700 KiB

sequence

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

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

static long long dp(void) {
  if (n <= 1)
    return 0LL;

  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;

    for (int i=(k1+2); i<=n; i++) {
      int last = offset[k1][i-1];
      int next = last + 1;

      long long val1 = prevrow[last] + psum[last] * (psum[i] - psum[last]);
      long long val2 = 0LL;

      while (next < i) {
        val2 = prevrow[next] + psum[next] * (psum[i] - psum[next]);
        if (val1 > val2)
          break;
        val1 = val2;
        next ++;
      }

      row[i] = val1;
      offset[k1][i] = next - 1;
    }

    /*
    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: 11 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29