結果

問題 No.1247 ブロック登り
ユーザー kk
提出日時 2021-04-14 20:03:29
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 522 ms / 3,000 ms
コード長 1,692 bytes
コンパイル時間 2,054 ms
コンパイル使用メモリ 201,180 KB
実行使用メモリ 215,172 KB
最終ジャッジ日時 2023-09-13 09:04:01
合計ジャッジ時間 10,068 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 58 ms
215,020 KB
testcase_01 AC 57 ms
215,168 KB
testcase_02 AC 57 ms
214,936 KB
testcase_03 AC 57 ms
215,092 KB
testcase_04 AC 57 ms
215,064 KB
testcase_05 AC 58 ms
215,124 KB
testcase_06 AC 58 ms
215,016 KB
testcase_07 AC 59 ms
214,880 KB
testcase_08 AC 60 ms
215,132 KB
testcase_09 AC 58 ms
215,060 KB
testcase_10 AC 59 ms
214,964 KB
testcase_11 AC 522 ms
214,940 KB
testcase_12 AC 437 ms
215,024 KB
testcase_13 AC 455 ms
214,968 KB
testcase_14 AC 453 ms
215,024 KB
testcase_15 AC 454 ms
214,908 KB
testcase_16 AC 462 ms
214,904 KB
testcase_17 AC 460 ms
214,900 KB
testcase_18 AC 411 ms
214,972 KB
testcase_19 AC 92 ms
215,064 KB
testcase_20 AC 70 ms
215,116 KB
testcase_21 AC 58 ms
215,076 KB
testcase_22 AC 63 ms
214,936 KB
testcase_23 AC 62 ms
215,004 KB
testcase_24 AC 57 ms
215,172 KB
testcase_25 AC 452 ms
215,040 KB
testcase_26 AC 448 ms
215,136 KB
testcase_27 AC 444 ms
214,904 KB
testcase_28 AC 461 ms
214,976 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