結果
問題 | No.2573 moving up |
ユーザー |
|
提出日時 | 2023-12-04 17:58:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 997 bytes |
コンパイル時間 | 1,757 ms |
コンパイル使用メモリ | 175,868 KB |
実行使用メモリ | 6,812 KB |
最終ジャッジ日時 | 2024-09-27 01:28:15 |
合計ジャッジ時間 | 2,881 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 RE * 1 |
ソースコード
#include<bits/stdc++.h>using namespace std;int main(){int H,W;cin>>H>>W;int base=0;priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> ap,dap;vector<int> Y(W);for(int i=0;i<W;i++){int x,y;cin>>x>>y;base+=x-1;ap.push({max(1,y-(x-1)),i});Y[i]=y;//cout<<max(1,y-(x-1))<<" "<<min(W+1,Y[i]+1)<<endl;}int rej=0,now=0;int extra=0;vector<short> seen(W,0);for(int i=1;i<=W;i++){while(ap.size() and ap.top().first==i){int idx=ap.top().second;ap.pop();seen[idx]++;now++;dap.push({min(W+1,Y[idx]+1),idx});}while(dap.size() and dap.top().first==i){int idx=dap.top().second;dap.pop();if(seen[idx]<2){now--;seen[idx]++;rej++;}}if(0<rej){extra+=(rej--);}else if(0<now){int idx=dap.top().second;now--;seen[idx]=2;dap.pop();}else{int idx=ap.top().first;extra+=ap.top().first - i;seen[idx]=2;ap.pop();}}cout<<base+extra<<"\n";}