Submission #971188

#	Time	Username	Problem	Language	Result	Execution time	Memory
971188		kilkuwu	Split the sequence (APIO14_sequence)	C++17	0 / 100	63 ms	22364 KiB

sequence

#include <bits/stdc++.h>

#define nl '\n'

const int mxN = 1e4 + 5, mxK = 205;
int way[mxN][mxK];
int N, K;

struct Line {
  int64_t a, b;
  int i;

  int64_t eval(int64_t x) const {
    return a * x + b;
  }

  int64_t intersect(const Line& rhs) const {
    auto a1 = a;
    auto a2 = rhs.a;
    auto b1 = b;
    auto b2 = rhs.b;
    return (b2 - b1) / (a1 - a2);
  }
};

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  std::cin >> N >> K;

  std::vector<int> A(N + 1);
  std::vector<int64_t> pref(N + 1);
  for (int i = 1; i <= N; i++) {
    std::cin >> A[i];
    pref[i] = pref[i - 1] + A[i];
  }
  std::vector<int64_t> dp(N + 1, -1e18);
  std::vector<int64_t> ndp(N + 1, -1e18);
  dp[0] = 0;

  for (int j = 1; j <= K + 1; j++) {
    std::deque<Line> dq;

    auto insert_line = [&](int64_t a, int64_t b, int i) -> void {
      // slope tang dan

      // add in the back
      // inter(line, line[-2]) <= inter(line[-1], line[-2])

      // a1x + b1 = ax + b
      // 

      Line l = {a, b, i};
      if (dq.empty()) {
        dq.push_back(l); 
      } else if (dq.size() == 1) {
        if (dq.back().a == a) {
          if (dq.back().b < b) {
            dq.back() = l;
          }
        } else {
          dq.push_back(l);
        }
      } else {
        while (dq.size() >= 2 && dq[dq.size() - 2].intersect(l) <= dq[dq.size() - 2].intersect(dq.back())) {
          dq.pop_back();
        }
        dq.push_back(l);
      }
    };

    auto query_point = [&](int64_t x) -> Line {
      while (dq.size() >= 2 && dq.front().eval(x) <= dq[1].eval(x)) {
        dq.pop_front();
      }
      return dq.front();
    };

    insert_line(pref[0], dp[0] - pref[0] * pref[0], 0);

    ndp[0] = -1e18;
    for (int i = 1; i <= N; i++) {
      auto line = query_point(pref[i]); 
      ndp[i] = line.eval(pref[i]);
      way[i][j] = line.i;
      insert_line(pref[i], dp[i] - pref[i] * pref[i], i);
    }

    std::swap(dp, ndp);
  }

  std::cout << dp[N] << nl;
  std::vector<int> ans;

  int x = N;
  int y = K + 1;
  while (x > 0 && y > 1) {
    ans.push_back(way[x][y]);
    x = way[x][y];
    y--;
  }

  for (int i : ans) std::cout << i << " ";
  std::cout << nl;
}


/*
7 3
4 1 3 4 0 2 3
*/

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