結果
問題 | No.929 よくあるボールを移動するやつ |
ユーザー | amaridekinai |
提出日時 | 2019-11-24 18:41:31 |
言語 | C++11 (gcc 11.4.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,016 bytes |
コンパイル時間 | 1,663 ms |
コンパイル使用メモリ | 166,940 KB |
実行使用メモリ | 11,812 KB |
最終ジャッジ日時 | 2024-10-12 04:21:14 |
合計ジャッジ時間 | 7,825 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
11,812 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 1 ms
6,816 KB |
testcase_03 | AC | 2 ms
6,816 KB |
testcase_04 | AC | 2 ms
6,820 KB |
testcase_05 | AC | 1 ms
6,820 KB |
testcase_06 | AC | 2 ms
6,816 KB |
testcase_07 | TLE | - |
testcase_08 | TLE | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
ソースコード
#include<bits/stdc++.h> using namespace std; typedef long long ll; vector<int> ans; int main(){ int n; cin >> n; vector<int> b(n); set<int> s; //2以上の要素があったらイテレータ管理 for(int i = 0; i < n ;i++){ cin >> b[i]; if( b[i] > 1){s.insert(i);} } int ans = 0; for(int i = 0; i < n; i++){ // b[0],,,b[i-1]まで1で揃えたものとする if( b[i] == 1){ continue;} if( b[i] > 1){ b[i+1] += b[i]-1; ans += b[i]-1; b[i] = 1; //1つだけ残して全て右へ移行 if(b[i+1] > 1){ s.insert(i+1);} //2つ以上になったら、重複を許さずにsにinsert } else if( b[i] == 0){ //位置iより右にある場所から、最も右に近い、2つ以上ある場所よりとってくる auto p = lower_bound(s.begin(),s.end(),i); int q = *p; if( b[q] == 2){ s.erase(p);} b[q]--; b[i]++; ans += q-i; } } cout << ans << endl; return 0; }