結果
問題 | No.1570 Blocks |
ユーザー |
![]() |
提出日時 | 2021-06-27 14:57:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 121 ms / 2,000 ms |
コード長 | 2,513 bytes |
コンパイル時間 | 3,331 ms |
コンパイル使用メモリ | 229,092 KB |
最終ジャッジ日時 | 2025-01-22 14:26:31 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 45 |
ソースコード
#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"; }