結果
問題 | No.2434 RAKUTAN de RAKUTAN |
ユーザー |
|
提出日時 | 2023-08-18 23:59:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 161 ms / 2,000 ms |
コード長 | 1,198 bytes |
コンパイル時間 | 1,331 ms |
コンパイル使用メモリ | 94,200 KB |
実行使用メモリ | 117,888 KB |
最終ジャッジ日時 | 2024-11-28 11:51:42 |
合計ジャッジ時間 | 3,338 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include<iostream>#include<vector>#include<map>#include<algorithm>using namespace std;int main() {int N,H,X,G,B;cin >> N >> H >> X >> G;map<int,int> m;m[0] = m[N] = 1;vector<int> g(G);for(int i=0;i<G;i++) {cin >> g[i];for(int j=-X;j<=X;j++)m[g[i]+j] = 1;}cin >> B;vector<int> b(B);for(int i=0;i<B;i++) {cin >> b[i];for(int j=-X;j<=X;j++)m[b[i]+j] = 1;}vector<int> v;for(auto i : m)v.push_back(i.first);sort(v.begin(),v.end());for(int i=0;i<v.size();i++)m[v[i]] = i;vector<int> t(v.size(),0),f(v.size(),false);for(int i=0;i<G;i++) {t[m[g[i]]]++;for(int j=-X;j<=0;j++)f[m[g[i]+j]] = true;}for(int i=0;i<B;i++) {t[m[b[i]]]--;for(int j=-X;j<=0;j++)f[m[b[i]+j]] = true;}vector<vector<int>> dp(v.size(),vector<int>(2020,0));dp[m[0]][1000] = H+1;for(int i=0;i<v.size()-1;i++)for(int j=0;j<2020;j++)if(dp[i][j]) {dp[i+1][j+t[i+1]] = max(dp[i+1][j+t[i+1]],dp[i][j]);if(f[i]) {int k = i;while(v[k] != v[i]+X)k++;dp[k][j+t[k]] = max(dp[k][j+t[k]],dp[i][j]-1);}}int ans = 0;for(int i=0;i<2020;i++)if(dp[m[N]][i])ans = i-1000;cout << ans << endl;}