제출 #1211767

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1211767		kunzaZa183	수열 (APIO14_sequence)	C++20	100 / 100	1400 ms	82996 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
  // cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);
  int n, k;
  cin >> n >> k;
  k++;
  vector<ll> vi(n);
  for (auto &a : vi) cin >> a;

  for (int i = 1; i < n; i++) vi[i] += vi[i - 1];

  // [..)
  auto qry = [&](int l, int r) {
    if (r == 0) return 0ll;
    if (l == 0) return vi[r - 1];
    return vi[r - 1] - vi[l - 1];
  };

  vector<vector<ll>> dp(2, vector<ll>(n + 1, -1e18));
  vector<vector<int>> bef(k + 1, vector<int>(n + 1, -1));

  dp[0][0] = 0;

  for (int div = 1; div <= k; div++) {
    queue<array<int, 4>> qai;
    qai.push({1, n, 0, n - 1});

    int cur = div % 2, other = 1 - div % 2;

    for (int i = 0; i < n + 1; i++) dp[cur][i] = -1e18;

    while (!qai.empty()) {
      auto [l, r, bl, br] = qai.front();
      qai.pop();

      if (l > r) continue;

      int mid = (l + r) / 2;

      assert(bl < mid);
      int bestin = bl;
      dp[cur][mid] = dp[other][bl] + qry(0, bl) * qry(bl, mid);
      for (int i = bl + 1; i <= br && i < mid; i++) {
        ll x = dp[other][i] + qry(0, i) * qry(i, mid);
        if (x > dp[cur][mid]) {
          dp[cur][mid] = x;
          bestin = i;
        }
      }
      bef[div][mid] = bestin;

      qai.push({l, (l + r) / 2 - 1, bl, bestin});
      qai.push({(l + r) / 2 + 1, r, bestin, br});
    }

    // for (auto a : dp[div]) cout << a << ' ';
    // cout << "\n";
  }

  // for (auto a : bef) {
  //   for (auto b : a) cout << b << " ";
  //   cout << "\n";
  // }

  cout << dp[k % 2][n] << "\n";

  int cur = n;
  for (int i = k; i > 1; i--) {
    cout << bef[i][cur] << " ";
    cur = bef[i][cur];
  }
  cout << "\n";
}

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