結果

問題 No.1247 ブロック登り
コンテスト
ユーザー k
提出日時 2021-04-14 20:03:29
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 1,119 ms / 3,000 ms
コード長 1,692 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,051 ms
コンパイル使用メモリ 194,080 KB
最終ジャッジ日時 2025-01-20 17:39:32
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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