Submission #238224

#	Time	Username	Problem	Language	Result	Execution time	Memory
238224		NONAME	Krov (COCI17_krov)	C++17	70 / 140	1598 ms	768 KiB

krov

#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 = 2e9;

        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) l = r = ri;
            if (fri < fle) r = ri;
            if (fle < fri) l = le;
        }

        ll cur = f(l, i);

        ans = (ans == -1 ? cur : min(ans, cur));
    }

    cout << ans;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14