結果
問題 |
No.1247 ブロック登り
|
ユーザー |
|
提出日時 | 2021-04-14 20:03:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,119 ms / 3,000 ms |
コード長 | 1,692 bytes |
コンパイル時間 | 2,051 ms |
コンパイル使用メモリ | 194,080 KB |
最終ジャッジ日時 | 2025-01-20 17:39:32 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#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; }