40012023-03-08 08:10:051478Sípálya (55 pont)cpp17Hibás válasz 29/55119ms24708 KiB
#include <bits/stdc++.h>

using namespace std;

int main()
{
    //ifstream cin("in.txt");
    long long n;
    cin >> n;
    long long k;
    cin >> k;
    vector<long long> heights(n + 2);
    vector<long long> ps(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> heights[i];
        ps[i] = ps[i - 1] + heights[i];
    }

    multiset<long long> s;
    for(int i = 1; i <= k; i++){
        s.insert(heights[i] + i);
    }

    long long ans = INT_MAX;
    for(long long i = k; i <= n; i++){
        long long actualsum = ps[i] - ps[i - k];
        long long neededsum = (*s.rbegin() * 2  - i * 2 + k - 1)*k/2 ;
        //cout << i << " " << heights[i] << " " << *s.rbegin() - i << " " << neededsum - actualsum << '\n';
        ans = min(ans, neededsum - actualsum);
        s.erase(s.lower_bound(heights[i - k + 1] + i - k + 1));
        s.insert(heights[i + 1] + i + 1);
    }
    cout << ans;



    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base29/55
1Elfogadva0/03ms1808 KiB
2Elfogadva0/03ms2060 KiB
3Elfogadva2/23ms2288 KiB
4Elfogadva2/23ms2440 KiB
5Elfogadva2/23ms2660 KiB
6Elfogadva2/23ms2876 KiB
7Elfogadva3/33ms3096 KiB
8Elfogadva1/18ms3456 KiB
9Elfogadva1/18ms3712 KiB
10Elfogadva1/18ms3924 KiB
11Elfogadva1/18ms4152 KiB
12Elfogadva1/18ms4448 KiB
13Elfogadva1/18ms4640 KiB
14Elfogadva2/28ms4852 KiB
15Elfogadva2/27ms4608 KiB
16Elfogadva2/2109ms10888 KiB
17Hibás válasz0/2114ms19724 KiB
18Hibás válasz0/2114ms20900 KiB
19Hibás válasz0/3114ms24708 KiB
20Elfogadva2/2114ms12080 KiB
21Hibás válasz0/2112ms11952 KiB
22Hibás válasz0/2112ms11956 KiB
23Elfogadva2/2112ms11432 KiB
24Hibás válasz0/2119ms11652 KiB
25Elfogadva2/2115ms12692 KiB
26Hibás válasz0/2115ms13032 KiB
27Hibás válasz0/2115ms13524 KiB
28Hibás válasz0/3114ms13348 KiB
29Hibás válasz0/3115ms13868 KiB
30Hibás válasz0/3115ms14384 KiB