Submission #117505

#	Time	Username	Problem	Language	Result	Execution time	Memory
117505		FutymyClone	Krov (COCI17_krov)	C++14	0 / 140	19 ms	1784 KiB

krov

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, a[N];

long long check (int mid) {
    long long sum = 0;
    int Min = 2e9 + 2277;
    for (int i = 1; i <= n; i++) {
        int need = a[mid] - abs(i - mid);
        sum += abs(need - a[i]);
        Min = min(Min, need);
    }

    if (Min <= 0) {
        sum = 0;
        for (int i = 1; i <= n; i++) {
            int need = a[mid] + 1 - Min - abs(i - mid);
            sum += abs(need - a[i]);
        }
    }
    return sum;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    //for (int i = 1; i <= n; i++) cout << check(i) << " ";
    //return 0;

    int l = 1, r = n;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid) < check(mid + 1)) r = mid - 1;
        else l = mid + 1;
    }

    cout << check(l);
    return 0;
}

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