結果
問題 | No.54 Happy Hallowe'en |
ユーザー |
|
提出日時 | 2017-01-03 20:01:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4,912 ms / 5,000 ms |
コード長 | 1,667 bytes |
コンパイル時間 | 1,192 ms |
コンパイル使用メモリ | 92,872 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-16 06:40:01 |
合計ジャッジ時間 | 100,037 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <numeric>#include <bitset>#include <memory>#include <chrono>#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)using namespace std;template <class T> void setmax(T & a, T const & b) { if (a < b) a = b; }template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; }int main() {chrono::high_resolution_clock::time_point clock_begin = chrono::high_resolution_clock::now();int n; cin >> n;vector<int> v(n), t(n); repeat (i,n) cin >> v[i] >> t[i];int ans_upper = 0;repeat (i,n) setmax(ans_upper, t[i]-1 + v[i]);setmin(ans_upper, whole(accumulate, v, 0));int ans = 0;auto dp = make_unique<bitset<2*10000+1> >();auto it = make_unique<bitset<2*10000+1> >();vector<int> ix(n); whole(iota, ix, 0);whole(iota, ix, 0);whole(sort, ix, [&](int i, int j) { return t[i] < t[j]; });while (true) {chrono::high_resolution_clock::time_point clock_end = chrono::high_resolution_clock::now();if (chrono::duration_cast<chrono::milliseconds>(clock_end - clock_begin).count() >= 4900) break;dp->reset();(*dp)[0] = true;for (int i : ix) {it->set();*it <<= t[i];it->flip();*it &= *dp;*it <<= v[i];*dp |= *it;}for (int i = ans_upper; i >= ans; -- i) {if ((*dp)[i]) setmax(ans, i);}whole(random_shuffle, ix);}cout << ans << endl;return 0;}