結果
問題 | 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;}