結果

問題 No.54 Happy Hallowe'en
ユーザー tnakao0123tnakao0123
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/* -*- 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0