結果
問題 | No.2423 Merge Stones |
ユーザー |
|
提出日時 | 2023-08-16 17:35:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 474 ms / 4,000 ms |
コード長 | 844 bytes |
コンパイル時間 | 1,975 ms |
コンパイル使用メモリ | 200,144 KB |
最終ジャッジ日時 | 2025-02-16 08:47:38 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 72 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll=long long;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int N,K;cin>>N>>K;vector A(N,0ll);vector C(N,0);for(auto &i:A)cin>>i;for(auto &i:C)cin>>i,--i;vector dp(N,vector(N+1,0ll));for(int i=0;i<N;i++){dp[i][1]=(1ll<<C[i]);}for(int i=2;i<=N;i++){for(int j=0;j<N;j++){for(int k=1;k<i;k++){for(int l=0;l<=K;l++){dp[j][i]|=(dp[j][k]&(dp[(j+k)%N][i-k]>>l));dp[j][i]|=((dp[j][k]>>l)&dp[(j+k)%N][i-k]);dp[j][i]|=(dp[j][k]&(dp[(j+k)%N][i-k]<<l));dp[j][i]|=((dp[j][k]<<l)&dp[(j+k)%N][i-k]);}}}}ll ans=0;for(int i=0;i<N;i++){ll t=0;for(int j=1;j<=N;j++){t+=A[(i+j-1)%N];if(dp[i][j])ans=max(ans,t);}}cout<<ans<<'\n';}