結果
問題 | No.2434 RAKUTAN de RAKUTAN |
ユーザー |
|
提出日時 | 2023-08-18 21:59:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 128 ms / 2,000 ms |
コード長 | 1,106 bytes |
コンパイル時間 | 1,205 ms |
コンパイル使用メモリ | 90,524 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-28 07:02:31 |
合計ジャッジ時間 | 2,671 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include<iostream> #include<algorithm> #include<vector> #include<queue> #include<cassert> #include<map> //#include<atcoder/modint> using namespace std; //using mint=atcoder::modint998244353; int N,H,X,G,B; map<int,int>mp; int dp[6][5001]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>N>>H>>X; mp[0]=0; mp[N]=0; cin>>G; for(;G--;) { int g;cin>>g; for(int i=max(g-X,0);i<=min(g+X,N);i++)mp[i]+=0; mp[g]+=1; } cin>>B; for(;B--;) { int g;cin>>g; for(int i=max(g-X,0);i<=min(g+X,N);i++)mp[i]+=0; mp[g]-=1; } vector<int>d; for(pair<int,int>p:mp)d.push_back(p.second); for(int i=0;i<=X;i++)for(int j=0;j<5000;j++)dp[i][j]=-1e9; dp[0][0]=0; for(int i=0;i+1<d.size();i++) { int ni=i%(X+1); int ti=ni<X?ni+1:0; int wi=ni>0?ni-1:X; if(i+X>=d.size())wi=-1; for(int j=0;j<5000;j++) { dp[ni][j]+=d[i]; dp[ti][j]=max(dp[ti][j],dp[ni][j]); if(wi>=0)dp[wi][j+1]=max(dp[wi][j+1],dp[ni][j]); dp[ni][j]=-1e9; } } int ans=-1e9; int ni=(d.size()-1)%(X+1); for(int j=0;j<5000&&j<=H;j++) { ans=max(ans,dp[ni][j]); } cout<<ans+d.back()<<endl; }