結果

問題 No.1247 ブロック登り
ユーザー kk
提出日時 2021-04-14 20:03:29
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 462 ms / 3,000 ms
コード長 1,692 bytes
コンパイル時間 2,085 ms
コンパイル使用メモリ 204,792 KB
実行使用メモリ 215,112 KB
最終ジャッジ日時 2024-06-30 18:53:51
合計ジャッジ時間 9,961 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 57 ms
214,940 KB
testcase_01 AC 58 ms
214,952 KB
testcase_02 AC 58 ms
214,932 KB
testcase_03 AC 58 ms
214,992 KB
testcase_04 AC 57 ms
215,032 KB
testcase_05 AC 57 ms
215,052 KB
testcase_06 AC 58 ms
214,948 KB
testcase_07 AC 60 ms
215,036 KB
testcase_08 AC 61 ms
214,984 KB
testcase_09 AC 59 ms
214,968 KB
testcase_10 AC 59 ms
214,896 KB
testcase_11 AC 453 ms
214,992 KB
testcase_12 AC 427 ms
215,020 KB
testcase_13 AC 448 ms
215,000 KB
testcase_14 AC 447 ms
214,816 KB
testcase_15 AC 450 ms
214,956 KB
testcase_16 AC 448 ms
214,964 KB
testcase_17 AC 456 ms
215,112 KB
testcase_18 AC 416 ms
215,028 KB
testcase_19 AC 92 ms
214,964 KB
testcase_20 AC 70 ms
214,980 KB
testcase_21 AC 59 ms
214,968 KB
testcase_22 AC 64 ms
214,988 KB
testcase_23 AC 62 ms
214,972 KB
testcase_24 AC 61 ms
214,952 KB
testcase_25 AC 446 ms
214,940 KB
testcase_26 AC 446 ms
215,040 KB
testcase_27 AC 446 ms
214,992 KB
testcase_28 AC 462 ms
214,952 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;
int N, K;
int a[300];
int dp[301][300][300][2];
int ret[300];

void init() {
  for (int k = 0; k <= 300; k++)
    for (int l = 0; l < 300; l++)
      for (int r = 0; r < 300; r++)
        for (int p = 0; p < 2; p++)
          dp[k][l][r][p] = -INF;

  for (int i = 0; i < 300; i++)
    ret[i] = -INF;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  init();
  
  cin >> N >> K;
  for (int i = 0; i < N; i++)
    cin >> a[i];

  for (int i = 0; i < N; i++)
    dp[K][i][i][0] = K * a[i];

  for (int k = K; k >= 0; k--) {
    for (int l = 0; l < N; l++) {
      for (int r = l; r < N; r++) {
        for (int p = 0; p < 2; p++) {
          int x = p == 0 ? l : r;

          // 解の更新
          if (x == l && x + k <= r)
            ret[x+k] = max(ret[x+k], dp[k][l][r][p]);
          if (x == r && l <= x - k)
            ret[x-k] = max(ret[x-k], dp[k][l][r][p]);

          // 動かない
          if (l < r && k >= 2) {
            dp[k-2][l][r][p] = max(dp[k-2][l][r][p], dp[k][l][r][p]);
          }

          // 反対側へ移動
          int dist = r - l;
          if (dist > 0 && k - dist >= 0) {
            dp[k-dist][l][r][!p] = max(dp[k-dist][l][r][!p], dp[k][l][r][p]);
          }

          // 領域外へ移動
          if (x == l && l > 0 && k > 0)
            dp[k-1][l-1][r][0] = max(dp[k-1][l-1][r][0], dp[k][l][r][p] + (k-1) * a[l-1]);
          if (x == r && r < N-1 && k > 0)
            dp[k-1][l][r+1][1] = max(dp[k-1][l][r+1][1], dp[k][l][r][p] + (k-1) * a[r+1]);
        }
      }
    }
  }
  
  for (int i = 0; i < N; i++)
    cout << ret[i] << endl;

  return 0;
}
0