Submission #53935

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

sequence

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

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

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

static tiii _dp(int s, int l, int k) {
  int m1, m1_j, m1_k1;

  for (int j=1; j<l; j++) {
    int s1 = (psum[s+j] - psum[s]) * (psum[s+l] - psum[s+j]);

    int m2, m2_k1;
    for (int k1=0; k1<k; k1++) {
      int s2 = std::get<0>(dp(s, j, k1)) + std::get<0>(dp(s+j, l-j, k-1-k1));

      if (k1 == 0 or s2 > m2) {
        m2 = s2;
        m2_k1 = k1;
      }
    }

    s1 += m2;
    if (j==1 or s1 > m1) {
      m1 = s1;
      m1_j = j;
      m1_k1 = m2_k1;
    }
  }

  return t3(m1, m1_j, m1_k1);
}

static tiii dp(int s, int l, int k) {
  if (l <= 1 or k <= 0)
    return t3(0, 0, 0);

  if (l == 2)
    return t3(A[s] * A[s+1], 1, 0);

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

  tiii 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;

  tiii x = dp(s, l, k);
  int j = std::get<1>(x);
  int k1 = std::get<2>(x);

  answer.push_back(s + j);

  recover(s, j, k1);
  recover(s+j, l-j, k - 1 - k1);
}

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 << std::get<0>(dp(0, n, k)) << 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;
}

Compilation message (stderr)

sequence.cpp: In function 'tiii dp(int, int, int)':
sequence.cpp:26:25: warning: 'm2' may be used uninitialized in this function [-Wmaybe-uninitialized]
       if (k1 == 0 or s2 > m2) {
                      ~~~^~~~
sequence.cpp:22:9: note: 'm2' was declared here
     int m2, m2_k1;
         ^~
sequence.cpp:33:14: warning: 'm1' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if (j==1 or s1 > m1) {
         ~~~~~^~~~~~~~~~
sequence.cpp:17:7: note: 'm1' was declared here
   int m1, m1_j, m1_k1;
       ^~

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