結果
問題 | No.929 よくあるボールを移動するやつ |
ユーザー |
![]() |
提出日時 | 2020-09-19 20:36:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 48 ms / 2,000 ms |
コード長 | 1,987 bytes |
コンパイル時間 | 2,028 ms |
コンパイル使用メモリ | 199,524 KB |
最終ジャッジ日時 | 2025-01-14 18:54:20 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 12 |
ソースコード
/*** code generated by JHelper* More info: https://github.com/AlexeyDmitriev/JHelper* @author aajisaka*/#include<bits/stdc++.h>using namespace std;void debug_out() { cerr << endl; }template <typename Head, typename... Tail>void debug_out(Head H, Tail... T) {cerr << " " << to_string(H);debug_out(T...);}#ifdef LOCAL#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)#else#define debug(...) 42#endif#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)#define rep(i,n) for(int i=0; i<(int)(n); i++)#define all(v) v.begin(), v.end()template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }using ll = long long;using ull = unsigned long long;using P = pair<ll, ll>;constexpr long double PI = 3.14159265358979323846264338327950288L;mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());class No929 {public:void solve(istream& cin, ostream& cout) {SPEED;int n; cin >> n;set<P> st;rep(i, n) {int b; cin >> b;if (b > 0) {st.emplace(i, b);}}ll ret = 0;rep(i, n) {auto it = st.lower_bound(P(i, 0));if (it != st.end()) {auto p = (*it);if (p.first == i) {st.erase(it);if (p.second > 1) {st.emplace(p.first, p.second - 1);}continue;}}if (it != st.begin()) {it--;}auto p2 = (*it);ret += abs(i - p2.first);st.erase(it);if (p2.second > 1) {st.emplace(p2.first, p2.second - 1);}}cout << ret << endl;}};signed main() {No929 solver;std::istream& in(std::cin);std::ostream& out(std::cout);solver.solve(in, out);return 0;}