77242024-01-10 18:28:22tamasmarkSípálya (55 pont)cpp17Hibás válasz 32/5597ms19740 KiB
// sipalya'.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <deque>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

int main()
{
    long long n, k;
    cin >> n >> k;
    vector<pair<long long,long long>>x(n + 1);
    priority_queue<pair<long long, long long>>p,p2;
    long long s1,s2,s3,mini=LONG_MAX,kulombseg;
    for (int i = 1; i <= n; ++i)
    {
        cin >> x[i].first;

        x[i].second = x[i - 1].second + x[i].first;
        p.push({ x[i].first,i });
        while (!p.empty() && p.top().second <= i - k)
        {
            p.pop();
        }
        if (p.top().first-x[i].first<i-p.top().second)
        {
            p2.push({ x[i].first,i });
            
        }
        while (!p2.empty() && p2.top().second <= i - k)
        {
            p2.pop();
        }
        if(!p2.empty())
            if(p.top().first==p2.top().first&&p.top().second==p2.top().second) p2.pop();
        if (i >= k)
        {
            x[i].second -= x[i - k].first;
            s1 = (p.top().second - (i - k + 1)) + p.top().first;
            if(!p2.empty()) s2 = p.top().first - ((p2.top().second-1) - p.top().second);
            else s2 = p.top().first - (i - p.top().second);
            if (!p2.empty())
            {
                kulombseg = p2.top().first - s2+1;
                s2 = p2.top().first - (i - p2.top().second);
                s1 += kulombseg;
                s3 = (((s1 + s2) * k) / 2)-x[i].second;
                //cout<<s3<<"\n";
            }
            else
            {
                 s3 = (((s1 + s2)*k)/2)-x[i].second;
                 //cout<<s3<<"\n";
            }
            mini = min(mini, s3);
        }
    }
    cout << mini;
    return 0;
}
/*
5 3
5 5 6 3 1
*/
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file
RészfeladatÖsszpontTesztVerdiktIdőMemória
base32/55
1Elfogadva0/03ms1816 KiB
2Elfogadva0/03ms2004 KiB
3Elfogadva2/24ms2400 KiB
4Elfogadva2/23ms2580 KiB
5Elfogadva2/23ms2564 KiB
6Elfogadva2/23ms2884 KiB
7Elfogadva3/33ms2844 KiB
8Hibás válasz0/17ms3728 KiB
9Hibás válasz0/17ms4080 KiB
10Hibás válasz0/17ms3932 KiB
11Elfogadva1/17ms3648 KiB
12Elfogadva1/17ms3668 KiB
13Elfogadva1/17ms3928 KiB
14Elfogadva2/27ms4020 KiB
15Elfogadva2/27ms3956 KiB
16Elfogadva2/292ms13720 KiB
17Hibás válasz0/283ms18148 KiB
18Hibás válasz0/282ms18360 KiB
19Hibás válasz0/390ms19740 KiB
20Elfogadva2/286ms18284 KiB
21Elfogadva2/287ms18292 KiB
22Elfogadva2/292ms18336 KiB
23Elfogadva2/290ms18596 KiB
24Elfogadva2/297ms18624 KiB
25Hibás válasz0/289ms18680 KiB
26Hibás válasz0/286ms18604 KiB
27Elfogadva2/285ms18632 KiB
28Hibás válasz0/386ms18728 KiB
29Hibás válasz0/385ms18600 KiB
30Hibás válasz0/386ms19024 KiB