結果
問題 | No.1570 Blocks |
ユーザー | suzuken_w |
提出日時 | 2021-06-27 14:57:29 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 112 ms / 2,000 ms |
コード長 | 2,513 bytes |
コンパイル時間 | 2,965 ms |
コンパイル使用メモリ | 226,636 KB |
実行使用メモリ | 11,396 KB |
最終ジャッジ日時 | 2023-09-07 17:56:42 |
合計ジャッジ時間 | 7,638 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 46 ms
9,944 KB |
testcase_03 | AC | 90 ms
10,628 KB |
testcase_04 | AC | 38 ms
7,708 KB |
testcase_05 | AC | 41 ms
7,744 KB |
testcase_06 | AC | 67 ms
7,864 KB |
testcase_07 | AC | 7 ms
4,376 KB |
testcase_08 | AC | 88 ms
10,768 KB |
testcase_09 | AC | 104 ms
11,056 KB |
testcase_10 | AC | 51 ms
10,360 KB |
testcase_11 | AC | 56 ms
10,576 KB |
testcase_12 | AC | 108 ms
11,220 KB |
testcase_13 | AC | 64 ms
11,136 KB |
testcase_14 | AC | 66 ms
11,092 KB |
testcase_15 | AC | 30 ms
6,936 KB |
testcase_16 | AC | 65 ms
11,396 KB |
testcase_17 | AC | 45 ms
6,900 KB |
testcase_18 | AC | 54 ms
10,312 KB |
testcase_19 | AC | 43 ms
7,012 KB |
testcase_20 | AC | 29 ms
6,976 KB |
testcase_21 | AC | 79 ms
10,296 KB |
testcase_22 | AC | 2 ms
4,376 KB |
testcase_23 | AC | 1 ms
4,380 KB |
testcase_24 | AC | 2 ms
4,376 KB |
testcase_25 | AC | 1 ms
4,376 KB |
testcase_26 | AC | 2 ms
4,376 KB |
testcase_27 | AC | 1 ms
4,376 KB |
testcase_28 | AC | 2 ms
4,380 KB |
testcase_29 | AC | 2 ms
4,380 KB |
testcase_30 | AC | 2 ms
4,380 KB |
testcase_31 | AC | 2 ms
4,380 KB |
testcase_32 | AC | 105 ms
11,192 KB |
testcase_33 | AC | 109 ms
11,112 KB |
testcase_34 | AC | 61 ms
10,768 KB |
testcase_35 | AC | 108 ms
11,064 KB |
testcase_36 | AC | 62 ms
11,172 KB |
testcase_37 | AC | 103 ms
11,088 KB |
testcase_38 | AC | 105 ms
11,232 KB |
testcase_39 | AC | 65 ms
11,112 KB |
testcase_40 | AC | 62 ms
11,080 KB |
testcase_41 | AC | 107 ms
11,072 KB |
testcase_42 | AC | 67 ms
11,256 KB |
testcase_43 | AC | 67 ms
11,372 KB |
testcase_44 | AC | 66 ms
11,160 KB |
testcase_45 | AC | 68 ms
11,260 KB |
testcase_46 | AC | 112 ms
11,176 KB |
ソースコード
#pragma GCC optimize("O3") #include<bits/stdc++.h> using namespace std; using ll=long long; using P=pair<ll,ll>; template<class T> using V=vector<T>; #define fi first #define se second #define all(v) (v).begin(),(v).end() const ll inf=(1e18); //const ll mod=998244353; const ll mod=1000000007; const vector<int> dy={-1,0,1,0},dx={0,-1,0,1}; ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;} ll LCM(ll c,ll d){return c/GCD(c,d)*d;} struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init; template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; } template<class T>void debag(const vector<T> &a){cerr<<"debag :";for(auto v:a)cerr<<v<<" ";cerr<<"\n";} template<class T>void print(const vector<T> &a){for(auto v:a)cout<<v<<" ";cout<<"\n";} template <typename T> struct ST{//1index query l,r lが開区間 using F = function<T(T,T)>; int n; F f; T ti; vector<T> dat; ST(){}; ST(F f,T ti):f(f),ti(ti){} void init(int n_){ n=1; while(n<n_) n<<=1; dat.assign(n<<1,ti); } void build(const vector<T> &v){ int n_=v.size(); init(n_); for(int i=0;i<n_;i++) dat[n+i]=v[i]; for(int i=n-1;i;i--) dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]); } void set_val(int k,T x){//kは0-index dat[k+=n]=x; while(k>>=1) dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]); } T query(int a,int b){ T vl=ti,vr=ti; for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) { if(l&1) vl=f(vl,dat[l++]); if(r&1) vr=f(dat[--r],vr); } return f(vl,vr); } }; int main(){ auto f=[&](P a,P b){ return max(a,b); }; int n; cin>>n; V<P> a(n); ll sum=0; V<ll> num; V<P> dat; for(int i=0;i<n;i++){ cin>>a[i].fi>>a[i].se; sum+=a[i].fi; num.emplace_back(a[i].fi+a[i].se); dat.emplace_back(a[i].fi+a[i].se,a[i].fi); } sort(all(num)); sort(all(dat)); ST<P> dp(f,P(0,-1)); dp.init(n+5); for(int i=0;i<n;i++){ dp.set_val(i,P(dat[i].se,i)); } int cnt=0; while(cnt<n){ int id=lower_bound(all(num),sum)-num.begin(); if(id==n){ cout<<"No"<<"\n"; return 0; } P p=dp.query(id,n); if(p.se==-1){ cout<<"No"<<"\n"; return 0; } sum-=p.fi; cnt++; dp.set_val(p.se,P(0,-1)); } cout<<"Yes"<<"\n"; }