結果
問題 | No.2423 Merge Stones |
ユーザー |
|
提出日時 | 2024-03-06 08:57:25 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,972 bytes |
コンパイル時間 | 1,339 ms |
コンパイル使用メモリ | 96,868 KB |
実行使用メモリ | 48,928 KB |
最終ジャッジ日時 | 2024-09-29 18:14:35 |
合計ジャッジ時間 | 6,861 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 TLE * 1 -- * 61 |
ソースコード
#include <iostream> #include <vector> using namespace std; using ll = long long; int main () { // 色と場所を持って区間dpできそう int N, K; cin >> N >> K; vector<int> A(N), C(N); for (int i = 0; i < N; i++) cin >> A[i]; for (int i = 0; i < N; i++) cin >> C[i]; for (int i = 0; i < N; i++) C[i]--; vector<vector<vector<ll>>> dp(N, vector<vector<ll>>(N+1, vector<ll>(50, 0))); // dp[i][j][c] := iから右回りにj個の区間を全統合し、結果色cの石を作ったとき、価値の最大 for (int i = 0; i < N; i++) dp[i][1][C[i]] = A[i]; for (int j = 2; j <= N; j++) { for (int i = 0; i < N; i++) { for (int c = 0; c < 50; c++) { for (int mid = 1; mid < j; mid++) { for (int k = 0; k <= K; k++) { if (0 < dp[i][mid][c] && 0 < dp[(i+mid)%N][j-mid][min(49, c+k)]) { dp[i][j][c] = max(dp[i][j][c], dp[i][mid][c] + dp[(i+mid)%N][j-mid][min(49, c+k)]); } if (0 < dp[i][mid][c] && 0 < dp[(i+mid)%N][j-mid][max(0, c-k)]) { dp[i][j][c] = max(dp[i][j][c], dp[i][mid][c] + dp[(i+mid)%N][j-mid][max(0, c-k)]); } if (0 < dp[i][mid][min(49, c+k)] && 0 < dp[(i+mid)%N][j-mid][c]) { dp[i][j][c] = max(dp[i][j][c], dp[i][mid][min(49, c+k)] + dp[(i+mid)%N][j-mid][c]); } if (0 < dp[i][mid][max(0, c-k)] && 0 < dp[(i+mid)%N][j-mid][c]) { dp[i][j][c] = max(dp[i][j][c], dp[i][mid][max(0, c-k)] + dp[(i+mid)%N][j-mid][c]); } } } } } } ll ans = 0; for (int i = 0; i < N; i++) for (int j = 1; j <= N; j++) for (int c = 0; c < 50; c++) ans = max(ans, dp[i][j][c]); cout << ans << "\n"; }