81872024-01-12 16:41:59szabelrSípálya (55 pont)cpp17Hibás válasz 18/55326ms5360 KiB
#include <iostream>

using namespace std;

int epit(int h[], int s, int K, int N) {
    int maxi = 0;
    for (int i = 0; i < K; i++)
        if (h[s+i]+i > h[s+maxi]+maxi) maxi = i;
    /* cout << "maxi = " << maxi << endl; */
    
    int m = h[s+maxi] - (K-1-maxi); // utolso lepcsofok magassaga
    /* cout << "m = " << m << endl; */
    
    int hs = 0;
    for (int i = 0; i < K; i++) hs += h[s+i];

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

int main() {

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

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

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

    for (int s = 1; s < N-K+1; s++) {
        /* int 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 (int 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];
        int p = K * (K-1) / 2 + K * m - hs;
        if (p < minp) minp = p;
    }
    cout << minp;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base18/55
1Elfogadva0/03ms3424 KiB
2Elfogadva0/04ms3664 KiB
3Elfogadva2/24ms3856 KiB
4Elfogadva2/24ms4068 KiB
5Elfogadva2/24ms4288 KiB
6Elfogadva2/24ms4352 KiB
7Hibás válasz0/34ms4332 KiB
8Elfogadva1/17ms4332 KiB
9Elfogadva1/17ms4480 KiB
10Elfogadva1/17ms4744 KiB
11Elfogadva1/114ms4624 KiB
12Elfogadva1/113ms4540 KiB
13Elfogadva1/121ms4496 KiB
14Elfogadva2/217ms4488 KiB
15Elfogadva2/212ms4636 KiB
16Hibás válasz0/2223ms4560 KiB
17Hibás válasz0/272ms4560 KiB
18Hibás válasz0/272ms4560 KiB
19Hibás válasz0/375ms4580 KiB
20Hibás válasz0/2112ms4560 KiB
21Hibás válasz0/2129ms4688 KiB
22Hibás válasz0/2215ms4696 KiB
23Hibás válasz0/2241ms4828 KiB
24Hibás válasz0/2326ms5064 KiB
25Hibás válasz0/2120ms5040 KiB
26Hibás válasz0/2135ms5040 KiB
27Hibás válasz0/274ms5044 KiB
28Hibás válasz0/382ms5168 KiB
29Hibás válasz0/374ms5252 KiB
30Hibás válasz0/374ms5360 KiB