Submission #563519

#TimeUsernameProblemLanguageResultExecution timeMemory
563519zxcvbnmLightning Conductor (POI11_pio)C++14
0 / 100
1086 ms9044 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; void self_max(int& me, int other) { me = max(me, other); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for(int& i : a) { cin >> i; } vector<int> ans(n, 0); for(int sz = 1, p = 1; p*p < n; p++, sz = p*p) { multiset<int> s(a.begin(), a.begin()+sz); auto rem = [&](int x) { s.erase(s.find(x)); }; //if (sz == 1) cout << p << " " << a[sz] << " " << *s.rend() << ": " << (p - a[sz] + *s.rend()) << "\n"; self_max(ans[sz], p - a[sz] + *s.rbegin()); for(int r = sz; r < n; r++) { rem(a[r-sz]); s.insert(a[r]); //if (r-sz == 1) cout << p << " " << a[r-sz] << " " << *s.rend() << "\n"; self_max(ans[r-sz], p - a[r-sz] + *s.rbegin()); if (r != n-1) { self_max(ans[r+1], p - a[r+1] + *s.rbegin()); //if (r+1 == 1) cout << p << " " << a[r+1] << " " << *s.rend() << "\n"; } } //for(int i : s) { //cout << i << " "; //} //cout << "\n"; } multiset<int> s; for(int i = 0; i < n-1; i++) { s.insert(a[i]); //cout << i+1 << ": " << ceil(sqrt(i+1)) << " " << a[i+1] << " " << *s.rbegin() << "\n"; self_max(ans[i+1], ceil(sqrt(i+1)) - a[i+1] + *s.rbegin()); } s.clear(); for(int i = n-1; i >= 1; i--) { s.insert(a[i]); self_max(ans[i-1], ceil(sqrt(n-i)) - a[i-1] + *s.rbegin()); } for(int i = 0; i < n; i++) { cout << ans[i] << "\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...
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...