結果
問題 | No.54 Happy Hallowe'en |
ユーザー |
![]() |
提出日時 | 2016-03-04 16:11:55 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 224 ms / 5,000 ms |
コード長 | 1,252 bytes |
コンパイル時間 | 855 ms |
コンパイル使用メモリ | 87,820 KB |
実行使用メモリ | 98,048 KB |
最終ジャッジ日時 | 2024-10-15 17:14:41 |
合計ジャッジ時間 | 2,843 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
/* -*- coding: utf-8 -*-** 54.cc: No.54 Happy Hallowe'en - yukicoder*/#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<iostream>#include<string>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<deque>#include<algorithm>#include<numeric>#include<utility>#include<complex>#include<functional>using namespace std;/* constant */const int MAX_N = 10000;const int MAX_T = 10000;/* typedef */struct VT {int v, t, sum;VT() {}VT(int _v, int _t): v(_v), t(_t) { sum = v + t; }bool operator<(const VT &vt) const { return sum < vt.sum; }};/* global variables */VT vts[MAX_N];bool dp[MAX_N + 1][MAX_T];/* subroutines *//* main */int main() {int n;cin >> n;for (int i = 0; i < n; i++) {int vi, ti;cin >> vi >> ti;vts[i] = VT(vi, ti);}sort(vts, vts + n);dp[0][0] = true;int ans = -1;for (int i = 0; i < n; i++) {int &vi = vts[i].v, &ti = vts[i].t;for (int j = 0; j < MAX_T; j++)if (dp[i][j]) {dp[i + 1][j] = true;if (j < ti) {int j0 = j + vi;if (ans < j0) ans = j0;if (j0 < MAX_T) dp[i + 1][j0] = true;}}}printf("%d\n", ans);return 0;}