8188 2024. 01. 12 16:48:08 szabelr Sípálya (55 pont) cpp17 Elfogadva 55/55 319ms 8276 KiB 
#include <iostream>

using namespace std;

long epit(long h[], long s, long K, long N) {
    long maxi = 0;
    for (long i = 0; i < K; i++)
        if (h[s + i] + i > h[s + maxi] + maxi) maxi = i;
    /* cout << "maxi = " << maxi << endl; */

    long m = h[s + maxi] - (K - 1 - maxi); // utolso lepcsofok magassaga
    /* cout << "m = " << m << endl; */

    long hs = 0;
    for (long i = 0; i < K; i++) hs += h[s + i];

    return K * (K - 1) / 2 + K * m - hs;
}

int main() {

    long N, K, h[200000];

    cin >> N >> K;
    for (long i = 0; i < N; i++) cin >> h[i];

    long maxi = 0;
    for (long i = 0; i < K; i++)
        if (h[i] + i > h[maxi] + maxi) maxi = i;
    long m = h[maxi] - (K - 1 - maxi); // utolso lepcsofok magassaga
    long hs = 0;
    for (long i = 0; i < K; i++) hs += h[i];

    long minp = K * (K - 1) / 2 + K * m - hs;

    for (long s = 1; s < N - K + 1; s++) {
        /* long p = epit(h, s, K, N); */

        if (maxi > 0) {
            if (h[s - 1 + maxi] + maxi - 1 > h[s + K - 1] + K - 1) maxi--;
            else maxi = K - 1;
        }
        else {
            maxi = 0;
            for (long i = 0; i < K; i++)
                if (h[s + i] + i > h[s + maxi] + maxi) maxi = i;
        }

        m = h[s + maxi] - (K - 1 - maxi); // utolso lepcsofok magassaga
        hs = hs - h[s - 1] + h[s + K - 1];
        long p = K * (K - 1) / 2 + K * m - hs;
        if (p < minp) minp = p;
    }
    cout << minp;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 55/55
1 Elfogadva 0/0 4ms 5116 KiB
2 Elfogadva 0/0 4ms 5484 KiB
3 Elfogadva 2/2 4ms 5612 KiB
4 Elfogadva 2/2 4ms 5708 KiB
5 Elfogadva 2/2 4ms 5880 KiB
6 Elfogadva 2/2 4ms 5788 KiB
7 Elfogadva 3/3 4ms 5792 KiB
8 Elfogadva 1/1 7ms 5916 KiB
9 Elfogadva 1/1 7ms 6132 KiB
10 Elfogadva 1/1 7ms 6364 KiB
11 Elfogadva 1/1 14ms 6288 KiB
12 Elfogadva 1/1 14ms 6416 KiB
13 Elfogadva 1/1 21ms 6560 KiB
14 Elfogadva 2/2 18ms 6656 KiB
15 Elfogadva 2/2 13ms 6628 KiB
16 Elfogadva 2/2 219ms 6628 KiB
17 Elfogadva 2/2 71ms 6884 KiB
18 Elfogadva 2/2 71ms 6972 KiB
19 Elfogadva 3/3 71ms 6984 KiB
20 Elfogadva 2/2 109ms 7056 KiB
21 Elfogadva 2/2 127ms 7152 KiB
22 Elfogadva 2/2 210ms 7268 KiB
23 Elfogadva 2/2 238ms 7472 KiB
24 Elfogadva 2/2 319ms 7548 KiB
25 Elfogadva 2/2 118ms 7736 KiB
26 Elfogadva 2/2 130ms 7808 KiB
27 Elfogadva 2/2 71ms 8028 KiB
28 Elfogadva 3/3 79ms 8120 KiB
29 Elfogadva 3/3 71ms 8040 KiB
30 Elfogadva 3/3 71ms 8276 KiB