Submission #238223

#TimeUsernameProblemLanguageResultExecution timeMemory
238223NONAMEKrov (COCI17_krov)C++17
56 / 140
1595 ms1664 KiB
#include <bits/stdc++.h> #define all(x) x.begin(), x.end() #define sz(x) int(x.size()) #define el '\n' #define pb push_back #define mp make_pair #define ft first #define sd second using namespace std; typedef long long ll; const int N = 1e5; int n, h[N]; ll ans = 0; ll f(ll x, int ps) { ll res = 0; for (int i = 0; i < n; ++i) res += abs(h[i] - abs(x - abs(ps - i))); return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 0; i < n; ++i) cin >> h[i]; ans = -1; for (int i = 0; i < n; ++i) { ll l = max(i + 1, n - i), r = 1e6; while (l < r) { ll ri = (l + r) >> 1; ll le = ri + 1; ll fri = f(ri, i); ll fle = f(le, i); if (fri < fle) r = ri; else l = le; } ll cur = f(l, i); ans = (ans == -1 ? cur : min(ans, cur)); } cout << ans; }
#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...