Submission #54175

#	Time	Username	Problem	Language	Result	Execution time	Memory
54175		nimar	Split the sequence (APIO14_sequence)	C++11	11 / 100	2078 ms	4252 KiB

sequence

#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <utility>
#include <tuple>

typedef std::tuple<int, int, int> tiii;
typedef std::pair<long long, int> li;
#define t3 std::make_tuple

static std::vector<int> A;
static std::vector<int> psum;
static std::map<tiii, li> DP;
static li dp(int s, int l, int k);

static li _dp(int s, int l, int k) {
  long long m = 0;
  int m_j = 0;

  for (int j=1; j<l; j++) {
    long long ans = (psum[s+j] - psum[s]) * (psum[s+l] - psum[s+j])
      + dp(s+j, l-j, k-1).first;

    if (j==1 or ans > m) {
      m = ans;
      m_j = j;
    }
  }

  return {m, m_j};
}

static li dp(int s, int l, int k) {
  if (l <= 1 or k <= 0)
    return {0LL, 0};

  if (l == 2)
    return {(long long) A[s] * A[s+1], 1};

  auto key = t3(s, l, k);
  auto it = DP.find(key);
  if (it != DP.end())
    return it->second;

  li val = _dp(s, l, k);
  DP[key] = val;
  return val;
}

static std::vector<int> answer;

static void recover(int s, int l, int k) {
  if (l <=1 or k <= 0)
    return;

  li x = dp(s, l, k);
  int j = x.second;

  answer.push_back(s + j);
  recover(s+j, l-j, k - 1);
}

int main(int argc, char const *argv[]) {
  int n, k;
  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(0, n, k).first << std::endl;
  recover(0, n, k);
  for (int a: answer)
    std::cout << a << " ";
  std::cout << std::endl;
  /*
  for (auto it = DP.begin(); it != DP.end(); it++)
    std::cout << "DP " << std::get<0>(it->first) << ", "
      << std::get<1>(it->first) << ", " << std::get<2>(it->first)
      << " = " << std::get<0>(it->second) << ", "<< std::get<1>(it->second)
      << ", " << std::get<2>(it->second) << '\n';
  std::cin >> n;
  */
  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