結果
問題 | No.54 Happy Hallowe'en |
ユーザー |
![]() |
提出日時 | 2021-10-21 20:58:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 565 ms / 5,000 ms |
コード長 | 724 bytes |
コンパイル時間 | 4,865 ms |
コンパイル使用メモリ | 255,024 KB |
最終ジャッジ日時 | 2025-01-25 02:33:41 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
#include <stdio.h>#include <bits/stdc++.h>#include <atcoder/all>using namespace atcoder;using mint = modint998244353;using namespace std;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf 1000000int main(){int n;cin>>n;vector<int> v(n),t(n);vector<pair<int,int>> p;rep(i,n){cin>>v[i]>>t[i];p.emplace_back(v[i]+t[i],i);}sort(p.begin(),p.end());vector<bool> dp(20005,false);dp[0] = true;rep(i,n){vector<bool> ndp(20005,false);rep(j,20005){if(dp[j]==false)continue;ndp[j] = true;if(j < t[p[i].second]){ndp[j + v[p[i].second]] = true;}}swap(dp,ndp);}int ans = 0;rep(i,dp.size()){if(dp[i])ans = i;}cout<<ans<<endl;return 0;}