結果
問題 | No.54 Happy Hallowe'en |
ユーザー |
![]() |
提出日時 | 2015-08-21 00:10:44 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 169 ms / 5,000 ms |
コード長 | 2,443 bytes |
コンパイル時間 | 1,351 ms |
コンパイル使用メモリ | 166,668 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-15 17:13:35 |
合計ジャッジ時間 | 2,870 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
#include <bits/stdc++.h>typedef long long ll;typedef unsigned long long ull;#define FOR(i,a,b) for(int (i)=(a);i<(int)(b);i++)#define REP(i,n) FOR(i,0,n)#define RANGE(vec) (vec).begin(),(vec).end()using namespace std;class HappyHalloween {public:void solve(void) {int N;cin>>N;int maxT = 0;int maxV = 0;vector<pair<int,int>> candy;REP(i,N){int v,t;cin>>v>>t;maxT = max(maxT,t);maxV = max(maxV,v);candy.emplace_back(v,t);}// 現在の candy の個数を C とするとき// C < T[a], C < T[b] として家 a, b を訪れるケースを考える。// a,b どちらが先でもキャンディをもらえるならどちらの順でもよいが、// そうでないケースを考える//// 1. a -> b 順でキャンディがもらえるとき C+V[a] < T[b]// 2. b -> a 順ではキャンディがもらえないとい C+V[b] >= T[a]//// 1,2 が同時に成り立つときは//// V[a]+T[a] < V[b]+T[b]//// となる。よって V[i]+T[i] でソートした順訪れれば良い。//// O(N*log(N))sort(RANGE(candy), [](const pair<int,int> &a, const pair<int,int> &b){return a.first+a.second < b.first+b.second;});// dp[C] := キャンディを C 個もらえるか?vector<bool> dp(maxV+maxT+1,false);// O(N*maxT)dp[0] = true;REP(i,N){int v = candy[i].first;// i のときの dp 更新を伝播させないために逆順にやる// C < T[i] のときしかもらえないので T[i]-1 からfor (int C = candy[i].second-1; C >= 0; --C)dp[v+C] = dp[v+C] | dp[C];}int C;for (C = dp.size()-1; C >= 0; --C)if (dp[C])break;cout<<C<<endl;}};#if 1int main(int argc, char *argv[]){ios::sync_with_stdio(false);auto obj = new HappyHalloween();obj->solve();delete obj;return 0;}#endif