結果
問題 | No.54 Happy Hallowe'en |
ユーザー |
![]() |
提出日時 | 2015-03-25 14:42:50 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3,534 ms / 5,000 ms |
コード長 | 1,448 bytes |
コンパイル時間 | 1,414 ms |
コンパイル使用メモリ | 167,532 KB |
実行使用メモリ | 395,012 KB |
最終ジャッジ日時 | 2024-10-15 17:11:40 |
合計ジャッジ時間 | 21,247 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
コンパイルメッセージ
main.cpp: In function ‘int solve(int)’: main.cpp:49:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 49 | scanf("%d%d", &v, &t); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp: In function ‘int main()’: main.cpp:65:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 65 | scanf("%d", &n); | ~~~~~^~~~~~~~~~
ソースコード
#include <bits/stdc++.h>using namespace std;#define endl '\n'#define all(v) (v).begin(), (v).end()#define rall(v) (v).rbegin(), (v).rend()#define uniq(v) (v).erase(unique((v).begin(), (v).end()), (v).end())typedef long long ll;typedef pair<int, int> P;typedef tuple<int, int, int> T;typedef unsigned int uint;typedef unsigned long long ull;struct pairhash {public:template<typename T, typename U>size_t operator()(const pair<T, U> &x) const {size_t seed = hash<T>()(x.first);return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);}};const int inf = 1000000009;const double eps = 1e-8;vector<T> vt;int memo[10001][10001];int calc(int sum, int num, int n) {int v = get<1>(vt[num]), t = get<2>(vt[num]);if (num == n-1) {return sum + (t > sum ? v : 0);} else {if (sum > 10000) return sum;if (memo[sum][num] < 0) {int res = 0;if (t > sum) {res = calc(sum+v, num+1, n);}memo[sum][num] = max(res, calc(sum, num+1, n));}return memo[sum][num];}}int solve(int n) {for (int i = 0; i < n; i++) {int v, t;scanf("%d%d", &v, &t);vt.push_back(make_tuple(v+t, v, t));}sort(all(vt));memset(memo, -1, sizeof(memo));return calc(0, 0, n);}int main() {/*ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(15);*/int n;scanf("%d", &n);printf("%d\n", solve(n));}