結果
問題 | No.2423 Merge Stones |
ユーザー |
![]() |
提出日時 | 2023-08-12 14:08:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 496 ms / 4,000 ms |
コード長 | 1,213 bytes |
コンパイル時間 | 1,070 ms |
コンパイル使用メモリ | 67,148 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-19 17:36:29 |
合計ジャッジ時間 | 27,458 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 72 |
ソースコード
//bitで作れる色の集合を持つと間に合いそう #include <iostream> #define int long long #define rep(i, n) for(i = 0; i < n; i++) using namespace std; int n, K; int a[600], ra[601]; int c[600]; int dp[601][601]; bool memo[601][601]; //[l, r) -> return: x (ibit目が1なら色i(>=0)にできる, 0なら色i(>=0)にできない) int dfs(int l, int r) { if (r - l == 1) { return (1LL << c[l]); } if (memo[l][r]) { return dp[l][r]; } int ret = 0; for (int i = l + 1; i < r; i++) { int res1 = dfs(l, i); int res2 = dfs(i, r); int res = 0; for (int j = 0; j <= K; j++) { res |= res1 & (res2 << j); res |= res2 & (res1 << j); } for (int j = 0; j <= K; j++) { res |= res1 & (res2 >> j); res |= res2 & (res1 >> j); } ret |= res; } memo[l][r] = true; return dp[l][r] = ret; } signed main() { int i, j; cin >> n >> K; rep(i, n) cin >> a[i]; rep(i, n) a[n + i] = a[i]; rep(i, 2 * n) ra[i + 1] = ra[i] + a[i]; rep(i, n) { cin >> c[i]; c[i]--; } rep(i, n) c[n + i] = c[i]; int ans = 0; rep(i, n) { for (j = 1; j <= n; j++) { int res = dfs(i, i + j); if (res > 0) { ans = max(ans, ra[i + j] - ra[i]); } } } cout << ans << endl; return 0; }