81712024-01-12 15:41:37bovizdbSípálya (55 pont)cpp17Futási hiba 0/55462ms7576 KiB
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define endl "\n"
#define pll pair<ll, ll>
#define fs first
#define sc second
#define vll vector<ll>
#define v2d vector<vector<ll>>
#define vpll vector<pll>
#define qll queue<ll>
#define stll stack<ll>
#define sll set<ll>
#define mll map<ll, ll>

ll solve()
{
    ll n, k;
    cin >> n >> k;
    vll h(n);
    for (ll i = 0; i < n; i++)
    {
        cin >> h[i];
    }
    if (k == 1)
    {
        cout << 0;
        return 0;
    }
    ll mx = 0, mxpos = 0;
    for (ll i = 0; i < k; i++)
    {
        if (h[i] > mx+(mxpos-i))
        {
            mx = h[i];
            mxpos = i;
        }
    }
    ll cost = 0;
    for (ll i = 0; i < k; i++)
    {
        cost += mx+(mxpos-i)-h[i];
    }
    ll out = cost;
    for (ll i = 1; i < n-k+1; i++)
    {
        cost -= mx+(mxpos-(i-1))-h[i-1];
        ll oldmx = mx, oldpos = mxpos;
        if (h[i+k-1] > mx+(mxpos-(i+k-1)))
        {
            cost += (k-1)*(h[i+k-1] - (mx+(mxpos-(i+k-1))));
            mx = h[i+k-1];
            mxpos = i+k-1;
        }
        else if (mxpos == i-1)
        {
            mx = 0;
            mxpos = 0;
            for (ll j = 0; j < k-1; j++)
            {
                if (h[i+j] > mx+(mxpos-(i+j)))
                {
                    mx = h[i+j];
                    mxpos = i+j;
                }
            }
            cost -= (k-1)*((oldmx+(oldpos-i)-h[i]) - (mx+(mxpos-i)-h[i]));
            cost += mx+(mxpos-(i+k-1))-h[i+k-1];
        }
        else
        {
            cost += mx+(mxpos-(i+k-1))-h[i+k-1];
        }
        out = min(out, cost);
    }
    cout  << out;
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll t = 1;
    //cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base0/55
1Futási hiba0/03ms1976 KiB
2Futási hiba0/03ms2232 KiB
3Futási hiba0/23ms2392 KiB
4Futási hiba0/23ms2356 KiB
5Futási hiba0/23ms2332 KiB
6Futási hiba0/23ms2456 KiB
7Futási hiba0/33ms2684 KiB
8Futási hiba0/14ms2824 KiB
9Futási hiba0/14ms3080 KiB
10Futási hiba0/14ms3280 KiB
11Futási hiba0/116ms3700 KiB
12Futási hiba0/114ms3648 KiB
13Futási hiba0/124ms3564 KiB
14Futási hiba0/218ms3752 KiB
15Futási hiba0/214ms4016 KiB
16Futási hiba0/2347ms6800 KiB
17Futási hiba0/228ms6668 KiB
18Futási hiba0/228ms7008 KiB
19Futási hiba0/329ms6968 KiB
20Futási hiba0/282ms6960 KiB
21Futási hiba0/2317ms6964 KiB
22Futási hiba0/2372ms7252 KiB
23Futási hiba0/2268ms7232 KiB
24Időlimit túllépés0/2462ms5008 KiB
25Futási hiba0/297ms7116 KiB
26Futási hiba0/2111ms7196 KiB
27Futási hiba0/2105ms7204 KiB
28Futási hiba0/359ms7264 KiB
29Futási hiba0/397ms7576 KiB
30Futási hiba0/329ms7488 KiB