Submission #236738

#TimeUsernameProblemLanguageResultExecution timeMemory
236738VEGAnnKrov (COCI17_krov)C++14
70 / 140
1591 ms1152 KiB
#include <bits/stdc++.h> #define sz(x) ((int)x.size()) #define ft first #define sd second using namespace std; typedef long long ll; const int N = 100100; const int oo = int(2e9); const ll OO = 1e18; const int md = int(1e9) + 7; int n; ll x[N], ans = OO; ll get(int id, ll ht){ ll cur = 0; for (int i = 0; i < n; i++) cur += abs(x[i] - (ht - abs(i - id))); return cur; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #ifdef _LOCAL freopen("in.txt","r",stdin); #endif // _LOCAL cin >> n; for (int i = 0; i < n; i++) cin >> x[i]; for (int i = 0; i < n; i++){ ll l = max(i + 1, n - i), r = ll(1e9); while (l + 5 < r){ ll md = (l + r) >> 1; if (get(i, md) < get(i, md + 1)) r = md; else l = md + 1; } for (ll j = l; j <= r; j++) ans = min(ans, get(i, j)); } cout << ans; 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...