結果

問題 No.54 Happy Hallowe'en
ユーザー simansiman
提出日時 2022-02-21 18:08:19
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 216 ms / 5,000 ms
コード長 1,152 bytes
コンパイル時間 2,653 ms
コンパイル使用メモリ 141,156 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-29 22:09:47
合計ジャッジ時間 4,695 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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

#include <cassert>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <climits>
#include <map>
#include <queue>
#include <set>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
struct Candy {
int v;
int t;
Candy(int v = -1, int t = -1) {
this->v = v;
this->t = t;
}
bool operator<(const Candy &n) const {
return v + t < (n.v + n.t);
}
};
int main() {
int N;
cin >> N;
for (int i = 0; i < N; ++i) {
}
vector<Candy> candy_list;
for (int i = 0; i < N; ++i) {
int v, t;
cin >> v >> t;
candy_list.push_back(Candy(v, t));
}
sort(candy_list.begin(), candy_list.end());
int dp[10010];
memset(dp, -1, sizeof(dp));
dp[0] = 0;
int ans = 0;
for (int i = 0; i < candy_list.size(); ++i) {
Candy candy = candy_list[i];
for (int v = 10000; v >= 0; --v) {
if (dp[v] == -1) continue;
int nv = v + candy.v;
int cnt = candy.v;
if (v >= candy.t) cnt = 1;
nv = min(nv, 10000);
dp[nv] = max(dp[nv], dp[v] + cnt);
ans = max(ans, dp[nv]);
}
}
cout << ans << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0