結果
問題 | 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"; }