結果
問題 | No.54 Happy Hallowe'en |
ユーザー |
![]() |
提出日時 | 2019-07-10 23:24:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 42 ms / 5,000 ms |
コード長 | 2,374 bytes |
コンパイル時間 | 2,047 ms |
コンパイル使用メモリ | 183,736 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-06 13:24:10 |
合計ジャッジ時間 | 3,311 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
#pragma GCC optimize("Ofast")#include <bits/stdc++.h>using namespace std;using i64=int_fast64_t;using pii=pair<int,int>;using pll=pair<i64,i64>;template <class T> constexpr T inf=numeric_limits<T>::max() / (T)2;template <class T> using heap=priority_queue<T>;template <class T> using minheap=priority_queue<T,vector<T>,greater<T>>;#define fir first#define sec second#define mkp make_pair#define mkt make_tuple#define emb emplace_back#define emp emplace#define all(v) begin(v),end(v)namespace std {template <class T> void hash_combine(size_t &seed, T const &key) {seed ^= hash<T>()(key) + 0x9e3779b9 + (seed << 6) + (seed >> 2);}template <class T, class U> struct hash<pair<T,U>> {size_t operator()(pair<T,U> const &pr) const{size_t seed = 0;hash_combine(seed,pr.first);hash_combine(seed,pr.second);return seed;}};}void ios_untie() {ios::sync_with_stdio(false);cin.tie(nullptr);}void file_setup() {if(!freopen("stderr.txt","wt",stderr)) {std::cerr << "Failed to open the stderr file\n";freopen("CON","wt",stderr);}if(!freopen("stdout.txt","wt",stdout)) {std::cerr << "Failed to open the stdout file\n";freopen("CON","wt",stdout);}if(!freopen("stdin.txt","rt",stdin)) {std::cerr << "Failed to open the stdin file.\n";freopen("CON","rt",stdin);}}template <class A, size_t N, class T> void init(A (&array)[N], const T &val) { fill((T*)array,(T*)(array + N),val); }i64 binry(i64 ok, i64 ng, const function<bool(i64)> &f) {while(abs(ok-ng)>1) {i64 mid=(ok+ng)/2;(f(mid) ? ok : ng) = mid;}return ok;}/*-------------------------------*/int n;pii ie[10010];bool dp[20010];void solve() {sort(ie,ie+n,[](pii a, pii b)->bool{ return a.fir+a.sec<b.fir+b.sec; });dp[0]=1;for(int i=0; i<n; ++i) {int v,t; tie(v,t)=ie[i];for(int j=t-1; j>=0; --j) {dp[j+v]|=dp[j];}}int ans=0;for(int i=0; i<=20000; ++i) {if(dp[i]) {ans=i;}}cout<<ans<<endl;}signed main() {ios_untie();#ifdef LOCALfile_setup();#endifcin>>n;for(int i=0; i<n; ++i) {cin>>ie[i].fir>>ie[i].sec;}solve();}