Submission #544645

#TimeUsernameProblemLanguageResultExecution timeMemory
544645pokmui9909전봇대 (KOI13_pole)C++17
100 / 100
21 ms2056 KiB
#include <string> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <vector> #include <deque> #include <functional> #include <climits> #include <set> #include <map> #include <cassert> #include <cmath> using namespace std; using ll = long long; ll n; ll ar[100005]; ll f(ll d) { ll ans = 0; for (ll i = 0; i < n; i++) ans += abs(d * i - ar[i]); return ans; } signed main() { cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false); cin >> n; for (int i = 0; i < n; i++) cin >> ar[i]; ll l = 0, r = ar[n - 1]; while (r - l >= 3) { ll p = (l * 2 + r) / 3, q = (l + r * 2) / 3; if (f(p) <= f(q)) r = q; else l = p; } ll ans = 1e15; for (int i = l; i <= r; i++) ans = min(ans, f(i)); 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...