結果
問題 | No.2423 Merge Stones |
ユーザー |
|
提出日時 | 2023-07-15 13:32:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 636 ms / 4,000 ms |
コード長 | 1,745 bytes |
コンパイル時間 | 991 ms |
コンパイル使用メモリ | 103,572 KB |
最終ジャッジ日時 | 2025-02-15 14:59:18 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 72 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:25:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 25 | scanf("%d", &A[i]); | ~~~~~^~~~~~~~~~~~~ main.cpp:33:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 33 | scanf("%d", &C[i]); | ~~~~~^~~~~~~~~~~~~
ソースコード
#include <iostream>#include <algorithm>#include <map>#include <set>#include <queue>#include <stack>#include <numeric>#include <bitset>#include <cmath>static const int MOD = 1000000007;using ll = long long;using uint = unsigned;using ull = unsigned long long;using namespace std;template<class T> constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;ll dp[600][601];int main() {int n, k;cin >> n >> k;vector<int> A(2*n), C(2*n);for (int i = 0; i < n; ++i) {scanf("%d", &A[i]);A[i+n] = A[i];}vector<ll> S(2*n+1);for (int i = 0; i < 2*n; ++i) {S[i+1] = S[i] + A[i];}for (int i = 0; i < n; ++i) {scanf("%d", &C[i]);C[i+n] = C[i];}n *= 2;for (int i = 0; i < n; ++i) {for (int j = i+1; j <= n; ++j) {dp[i][j] = 0;}dp[i][i+1] = (1LL << C[i]);}for (int len = 2; len <= n; ++len) {for (int l = 0; l+len <= n; ++l) {int r = l+len;for (int mid = l+1; mid < r; ++mid) {ll lval = dp[l][mid], rval = dp[mid][r];if(lval == 0 || rval == 0) continue;dp[l][r] |= lval & rval;for (int i = 1; i <= k; ++i) {dp[l][r] |= lval & (rval << i);dp[l][r] |= lval & (rval >> i);dp[l][r] |= lval << i & rval;dp[l][r] |= lval >> i & rval;}}}}ll ans = 0;for (int i = 0; i < n; ++i) {for (int j = i+1; j <= n && j-i <= n/2; ++j) {if(dp[i][j] > 0) ans = max(ans, S[j]-S[i]);}}cout << ans << "\n";return 0;}