結果
問題 | No.54 Happy Hallowe'en |
ユーザー |
![]() |
提出日時 | 2020-11-13 23:45:16 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 251 ms / 5,000 ms |
コード長 | 2,454 bytes |
コンパイル時間 | 2,715 ms |
コンパイル使用メモリ | 171,536 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-22 22:19:12 |
合計ジャッジ時間 | 4,627 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
#include <bits/stdc++.h>//#include <atcoder/all>//using namespace atcoder;#pragma GCC target ("avx2")#pragma GCC optimization ("O3")#pragma GCC optimization ("unroll-loops")const double pi = 3.141592653589793238462643383279;using namespace std;//typedef//------------------------------------------typedef vector<int> VI;typedef vector<VI> VVI;typedef vector<string> VS;typedef pair<int, int> PII;typedef pair<long long, long long> PLL;typedef pair<int, PII> TIII;typedef long long LL;typedef unsigned long long ULL;typedef vector<LL> VLL;typedef vector<VLL> VVLL;//container util//------------------------------------------#define ALL(a) (a).begin(), (a).endf()#define RALL(a) (a).rbegin(), (a).rend()#define PB push_back#define MP make_pair#define SZ(a) int((a).size())#define SQ(a) ((a) * (a))#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).endf(); ++i)#define EXIST(s, e) ((s).find(e) != (s).endf())#define SORT(c) sort((c).begin(), (c).endf())//repetition//------------------------------------------#define FOR(i, s, n) for (int i = s; i < (int)n; ++i)#define REP(i, n) FOR(i, 0, n)#define MOD 1000000007#define rep(i, a, b) for (int i = a; i < (b); ++i)#define trav(a, x) for (auto &a : x)#define all(x) x.begin(), x.end()typedef long long ll;typedef pair<int, int> pii;typedef vector<int> vi;#define chmin(x, y) x = min(x, y)#define chmax(x, y) x = max(x, y)const double EPS = 1e-4, PI = acos(-1);//ここから編集typedef string::const_iterator State;int dp[2][10101];int main() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);int N; cin >> N;vector<int> V(N), T(N);REP(i,N) cin >> V[i] >> T[i];vector<pair<int, pair<int, int>>> vp;REP(i,N){vp.push_back(make_pair(V[i]+T[i], make_pair(T[i], V[i])));}sort(all(vp));int mx = 0;REP(i,10101) dp[0][i] = dp[1][i] = -1;dp[0][0] = 0;REP(i,N){int t, v;tie(t, v) = vp[i].second;for(int j=0; j<=10000; j++){if(dp[i%2][j] == -1) continue;if(j < t){if(j+v>10000){mx = max(mx, dp[i%2][j] + v);}else{dp[(i+1)%2][j+v] = max(dp[(i+1)%2][j+v], dp[i%2][j] + v);mx = max(mx, dp[(i+1)%2][j+v]);}}dp[(i+1)%2][j] = max(dp[(i+1)%2][j], dp[i%2][j]);}}cout << mx << endl;return 0;}