제출 #1076966

#제출 시각아이디문제언어결과실행 시간메모리
1076966bleahbleahTortoise (CEOI21_tortoise)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; #define _ << " " << const int MAXN = 5e5 + 5; const int off = 1 << 19; const int inf = 1e9; #define int long long int a[MAXN]; int l[MAXN]; int r[MAXN]; int before[MAXN]; unordered_map<int, int> specialChair; typedef pair<int, int> pii; bool possible(multiset<int> s) { int last = -1, timer = 0; for(auto x : s) { if(last == -1) { timer += x; } else { if(l[last] != l[x] || r[last] != r[x]) timer += x - last; else timer += min(last - l[last] + x - l[last], r[last] - last + r[last] - x); } if(timer > 2 * (x)) { return 0; } last = x; //cerr << timer << '\n'; } //cerr << '\n'; //for(auto x: s) cerr << x << ' '; cerr << '\n'; //cerr << "ok\n"; return 1; } long long sum; multiset<int> TT; void solve(int x, int d, int type) { int cnt = 0; while(a[x] > 0) { TT.insert(x); if(possible(TT)) { a[x] --; sum --; cnt ++; } else { TT.erase(TT.find(x)); break; } } } signed main() { int n; cin >> n; for (int i = 0; i < n; ++i) { cin >> a[i]; if (a[i] != -1) sum += a[i]; } int tmp = -1; for (int i = 0; i < n; ++i) { if (a[i] == -1) { tmp = i; } l[i] = tmp; } tmp = -1; for (int i = n - 1; i >= 0; --i) { if (a[i] == -1) { tmp = i; } r[i] = tmp; } vector<pair<int, pii>> candidates; for (int i = 0; i < n; ++i) { if (a[i] > 0) { if (r[i] != -1) { candidates.push_back({r[i] - i, {i, 1}}); } if (l[i] != -1) { candidates.push_back({i - l[i], {i, 0}}); } } } sort(candidates.begin(), candidates.end()); for (auto candidate : candidates) { int x = candidate.second.first; int d = candidate.first; int type = candidate.second.second; solve(x, d, type); } sum =0; for (int i = 0; i < n; ++i) { //cerr << a[i] << ' '; if (a[i] != -1) sum += a[i]; } cerr << '\n'; cout << sum << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...