結果
問題 |
No.1734 Decreasing Elements
|
ユーザー |
![]() |
提出日時 | 2021-12-28 00:43:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 682 ms / 3,000 ms |
コード長 | 900 bytes |
コンパイル時間 | 2,990 ms |
コンパイル使用メモリ | 184,692 KB |
実行使用メモリ | 42,388 KB |
最終ジャッジ日時 | 2024-10-01 11:48:29 |
合計ジャッジ時間 | 14,483 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ int N,A,K,ans=0,range=3e5; set<int> s; auto comp=[](vector<int> a,vector<int> b){ return a[1]<b[1]; }; priority_queue<vector<int>,vector<vector<int>>,decltype(comp)> q{comp}; queue<vector<int>> temp; cin>>N; s.insert(0); q.push((vector<int>){0,range}); for(int i=0;i<N;++i){ cin>>A; auto j=s.lower_bound(A); if(j!=s.end()&&*j==A){ continue; } --j; K=A-*j; while(!q.empty()&&q.top()[1]>K){ vector<int> v=q.top(); s.insert(v[0]+K); temp.push((vector<int>){v[0]+K,v[1]-K}); temp.push((vector<int>){v[0],K}); q.pop(); } while(!temp.empty()){ q.push(temp.front()); temp.pop(); } ++ans; } cout<<ans<<endl; }