結果
問題 | No.54 Happy Hallowe'en |
ユーザー |
|
提出日時 | 2014-10-31 01:33:05 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 57 ms / 5,000 ms |
コード長 | 1,476 bytes |
コンパイル時間 | 511 ms |
コンパイル使用メモリ | 68,196 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-15 17:09:38 |
合計ジャッジ時間 | 1,441 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
// 想定解法: DP#include <iostream>#include <vector>#include <set>#include <algorithm>using namespace std;#define REP(i, n) for(int(i)=0;(i)<(n);++(i))#define RREP(i, n) for(int(i)=(n)-1;(i)>=0;--(i))void rc(int v,int mn,int mx){if(v<mn||mx<v){cerr<<"error"<<endl;}}const int MAXN = 10000;const int MAXV = 10000;const int MAXT = 10000;int N,V,T;set<int> s[MAXT*2+1];bool dp[MAXT*2+1];pair<int,int> p;int main(){cin >> N; rc(N,1,MAXN);int maxt = 0;REP(i,N){cin >> V >> T; rc(V,1,MAXV); rc(T,1,MAXT);s[T+V].insert(T);maxt = max(maxt, T+V);}dp[0] = true;int res = 0;REP(i,maxt+1){for(auto it = s[i].begin(); it != s[i].end(); ++it){int v = i - *it;RREP(j,*it){int k = j+v;if(dp[j]){if(k < MAXT*2) dp[k] = true;res = max(res, k);}}}}cout << res << endl;return 0;}/* 解説T+Vが小さい順にソートしてDP家1がV1 T1、家2がV2 T2だとすると家1に行った場合の所持数の可能性が[V1,V1+T1-1]の範囲、家1に行った場合の所持数の可能性が[V2,V2+T2-1]の範囲となる。なので、行った結果の所持数の最大が小さい順にDP自信がないけどたぶん(´・_・`)*/