結果

問題 No.1117 数列分割
ユーザー keijakkeijak
提出日時 2020-07-17 22:33:03
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,121 bytes
コンパイル時間 2,398 ms
コンパイル使用メモリ 207,800 KB
実行使用メモリ 73,728 KB
最終ジャッジ日時 2024-11-30 03:42:36
合計ジャッジ時間 38,419 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,496 KB
testcase_01 AC 2 ms
26,880 KB
testcase_02 AC 2 ms
10,496 KB
testcase_03 AC 55 ms
40,832 KB
testcase_04 AC 475 ms
13,312 KB
testcase_05 AC 1 ms
49,024 KB
testcase_06 AC 2 ms
10,496 KB
testcase_07 AC 3 ms
12,544 KB
testcase_08 AC 1,427 ms
12,544 KB
testcase_09 AC 141 ms
5,248 KB
testcase_10 AC 1,877 ms
7,552 KB
testcase_11 TLE -
testcase_12 AC 2,408 ms
23,040 KB
testcase_13 AC 1,102 ms
30,720 KB
testcase_14 TLE -
testcase_15 AC 368 ms
39,168 KB
testcase_16 TLE -
testcase_17 TLE -
testcase_18 AC 51 ms
73,600 KB
testcase_19 AC 51 ms
73,600 KB
testcase_20 TLE -
testcase_21 AC 51 ms
73,728 KB
testcase_22 AC 1,193 ms
73,088 KB
testcase_23 AC 1,250 ms
73,088 KB
testcase_24 AC 2,372 ms
71,936 KB
testcase_25 AC 2,450 ms
71,936 KB
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
#define REP(i, n) for (int i = 0; (i64)(i) < (i64)(n); ++i)

#ifdef ENABLE_DEBUG
template <typename T>
void debug(T value) {
  cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  cerr << value << ", ";
  debug(args...);
}
#define DEBUG(...)                              \
  do {                                          \
    cerr << " \033[33m (L" << __LINE__ << ") "; \
    cerr << #__VA_ARGS__ << ":\033[0m ";        \
    debug(__VA_ARGS__);                         \
    cerr << endl;                               \
  } while (0)
#else
#define debug(...)
#define DEBUG(...)
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  i64 N, K, M;
  cin >> N >> K >> M;
  vector<i64> A(N);
  for (auto& x : A) cin >> x;

  // vector<vector<vector<i64>>> dp(n + 1, vector<vector<i64>>(m,
  // vector<i64>(2)));

  vector<vector<i64>> memo(N + 1, vector<i64>(K + 1, -1));
  auto f = [&](auto rec, int len, int block_count) -> i64 {
    if (len == 0 || block_count == 0) return 0;
    if (len < block_count) return 0;
    if (memo[len][block_count] >= 0) return memo[len][block_count];
    if (len == block_count) {
      i64 sum = 0;
      for (int i = 0; i < len; ++i) {
        sum += abs(A[i]);
      }
      DEBUG(len, block_count, sum);
      return (memo[len][block_count] = sum);
    }
    if (block_count == 1) {
      i64 sum = 0;
      for (int i = 0; i < len; ++i) {
        sum += A[i];
      }
      return (memo[len][block_count] = abs(sum));
    }
    int m = min<int>(M, len);
    i64 max_score = 0;
    i64 block_sum = 0;
    for (int x = 1; x <= m; ++x) {
      assert(len - x >= 0);
      assert(len - x < N);
      block_sum += A[len - x];
      i64 r = rec(rec, len - x, block_count - 1);
      max_score = max(max_score, r + abs(block_sum));
      if (len == 4) {
        DEBUG(len, block_count, x, block_sum, r, max_score);
      }
    }
    return (memo[len][block_count] = max_score);
  };
  i64 ans = f(f, N, K);
  cout << ans << endl;
}
0