40012023-03-08 08:10:051478Sípálya (55 pont)cpp17Wrong answer 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;
}
SubtaskSumTestVerdictTimeMemory
base29/55
1Accepted0/03ms1808 KiB
2Accepted0/03ms2060 KiB
3Accepted2/23ms2288 KiB
4Accepted2/23ms2440 KiB
5Accepted2/23ms2660 KiB
6Accepted2/23ms2876 KiB
7Accepted3/33ms3096 KiB
8Accepted1/18ms3456 KiB
9Accepted1/18ms3712 KiB
10Accepted1/18ms3924 KiB
11Accepted1/18ms4152 KiB
12Accepted1/18ms4448 KiB
13Accepted1/18ms4640 KiB
14Accepted2/28ms4852 KiB
15Accepted2/27ms4608 KiB
16Accepted2/2109ms10888 KiB
17Wrong answer0/2114ms19724 KiB
18Wrong answer0/2114ms20900 KiB
19Wrong answer0/3114ms24708 KiB
20Accepted2/2114ms12080 KiB
21Wrong answer0/2112ms11952 KiB
22Wrong answer0/2112ms11956 KiB
23Accepted2/2112ms11432 KiB
24Wrong answer0/2119ms11652 KiB
25Accepted2/2115ms12692 KiB
26Wrong answer0/2115ms13032 KiB
27Wrong answer0/2115ms13524 KiB
28Wrong answer0/3114ms13348 KiB
29Wrong answer0/3115ms13868 KiB
30Wrong answer0/3115ms14384 KiB