結果
問題 | No.54 Happy Hallowe'en |
ユーザー | Ysmr_Ry |
提出日時 | 2014-12-13 19:28:54 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 871 bytes |
コンパイル時間 | 580 ms |
コンパイル使用メモリ | 59,972 KB |
実行使用メモリ | 394,244 KB |
最終ジャッジ日時 | 2023-09-02 14:27:41 |
合計ジャッジ時間 | 23,637 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 233 ms
393,660 KB |
testcase_01 | AC | 237 ms
393,640 KB |
testcase_02 | AC | 226 ms
393,636 KB |
testcase_03 | AC | 227 ms
393,692 KB |
testcase_04 | AC | 480 ms
393,780 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | AC | 226 ms
393,640 KB |
testcase_11 | AC | 227 ms
393,560 KB |
testcase_12 | AC | 2,028 ms
394,236 KB |
testcase_13 | WA | - |
testcase_14 | AC | 230 ms
393,636 KB |
testcase_15 | AC | 228 ms
393,692 KB |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
ソースコード
#include<cstdio> #include<cstring> #include<algorithm> #include<functional> #include<utility> #define rep(i,a) for(int i=0;i<(a);++i) #define clr(a,v) memset((a),(v),sizeof(a)) typedef std::pair<int, int> P; const int MAX_N = 10000; int N; P ps[MAX_N]; int dp[MAX_N][MAX_N+1]; int rec( int i, int c ) { if( i == N ) return c; int &ret = dp[i][c]; if( ~ret ) return ret; if( c >= ps[i].first ) return ret = rec( i+1, c ); else return ret = std::max( rec( i+1, c ), rec( i+1, std::min( MAX_N, c+ps[i].second ) ) ); } int main() { scanf( "%d", &N ); rep( i, N ) { int V, T; scanf( "%d%d", &V, &T ); ps[i] = P( T, V ); } std::sort( ps, ps+N, []( const P &lhs, const P &rhs ){ return lhs.first+lhs.second < rhs.first+rhs.second; } ); clr( dp, -1 ); printf( "%d\n", rec( 0, 0 ) ); return 0; }