Submission #289741

#TimeUsernameProblemLanguageResultExecution timeMemory
289741HynDufLightning Conductor (POI11_pio)C++14
100 / 100
286 ms14164 KiB
#include <bits/stdc++.h> #define task "C" #define all(v) (v).begin(), (v).end() #define rep(i, l, r) for (int i = (l); i <= (r); ++i) #define Rep(i, r, l) for (int i = (r); i >= (l); --i) #define DB(X) { cerr << #X << " = " << (X) << '\n'; } #define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; } #define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; } #define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; } #define PR(A, l, r) { cerr << '\n'; rep(_, l, r) DB1(A, _); cerr << '\n';} #define SZ(x) ((int)(x).size()) #define pb push_back #define eb emplace_back #define pf push_front #define F first #define S second #define by(x) [](const auto& a, const auto& b) { return a.x < b.x; } // sort(arr, arr + N, by(a)); #define next ___next #define prev ___prev #define y1 ___y1 #define left ___left #define right ___right #define y0 ___y0 #define div ___div #define j0 ___j0 #define jn ___jn using ll = long long; using ld = long double; using ull = unsigned long long; using namespace std; typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<ll> vl; const int N = 5e5 + 2; int n, h[N], sq[N], dp[N]; int cost(int i, int j) { return h[j] + sq[abs(i - j)]; } ld costd(int i, int j) { return h[j] + (ld) (sqrt(abs(i - j))); } void cal(int l, int r, int optl, int optr) { if (l > r) return; int m = (l + r) >> 1, opt = optl; rep(k, optl + 1, min(m, optr)) if (costd(m, k) > costd(m, opt)) opt = k; dp[m] = max(dp[m], cost(m, opt)); cal(l, m - 1, optl, opt); cal(m + 1, r, opt, optr); } int main() { #ifdef HynDuf freopen(task".in", "r", stdin); //freopen(task".out", "w", stdout); #else ios_base::sync_with_stdio(false); cin.tie(nullptr); #endif cin >> n; rep(i, 1, n) cin >> h[i]; rep(i, 1, 708) { if (i * i >= n) { sq[n] = i; break; } sq[i * i] = i; } Rep(i, n - 1, 2) if (!sq[i]) sq[i] = sq[i + 1]; cal(1, n, 1, n); reverse(h + 1, h + 1 + n); reverse(dp + 1, dp + 1 + n); cal(1, n, 1, n); Rep(i, n, 1) cout << dp[i] - h[i] << '\n'; return 0; }
#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...