結果
問題 | No.1570 Blocks |
ユーザー |
|
提出日時 | 2021-06-27 17:07:06 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 59 ms / 2,000 ms |
コード長 | 1,206 bytes |
コンパイル時間 | 921 ms |
コンパイル使用メモリ | 81,220 KB |
実行使用メモリ | 7,252 KB |
最終ジャッジ日時 | 2024-06-25 11:52:53 |
合計ジャッジ時間 | 3,952 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 45 |
ソースコード
#include <iostream>#include <cstring>#include <algorithm>#include <queue>#include <vector>#define ll long longusing namespace std;const int maxn=1e5+100;struct node{int id;ll w, carry;bool operator < (const node& x)const{return w<x.w;}};bool cmp(node a,node b){return a.carry<b.carry;}node box[maxn];priority_queue<node> q;int main(){ios::sync_with_stdio(false);int N;cin>>N;ll sum=0;for(int i=1;i<=N;i++){cin>>box[i].w>>box[i].carry;box[i].carry+=box[i].w;sum+=box[i].w;}sort(box+1,box+1+N,cmp);int cnt=0;int last=N;while(cnt<N){int L=1;int R=N-cnt;while(L<=R){int mid=(L+R)>>1;if(box[mid].carry>=sum){R=mid-1;}else{L=mid+1;}}ll w=-1;int id=-1;for(int i=L;i<=last;i++){q.push(box[i]);}last=L-1;if(q.empty()) break;node x=q.top();q.pop();sum-=x.w;cnt+=1;}if(cnt==N){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}return 0;}