Submission #1294135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294135		SSKMF	Feast (NOI19_feast)	C++20	100 / 100	82 ms	2052 KiB

feast

#include <bits/stdc++.h>
using namespace std;

int sir[300001];

int main()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int lungime , limita;
    cin >> lungime >> limita;

    for (int indice = 1 ; indice <= lungime ; indice++)
        { cin >> sir[indice]; }
    
    int64_t stanga = -1e15 , dreapta = 0 , rezultat = 0;
    while (stanga <= dreapta)
    {
        pair <int64_t , int> maxim[2] = {{-1e15 , 0} , {0 , 0}};
        const int64_t termen = (stanga + dreapta) / 2;
        for (int indice = 1 ; indice <= lungime ; indice++)
        {
            if (maxim[0].first > maxim[1].first + termen || (maxim[0].first == maxim[1].first + termen && maxim[0].second < maxim[1].second + 1))
                { maxim[0] = {maxim[0].first + sir[indice] , maxim[0].second}; }
            else
                { maxim[0] = {maxim[1].first + termen + sir[indice] , maxim[1].second + 1}; }

            if (maxim[1].first < maxim[0].first || (maxim[1].first == maxim[0].first && maxim[0].second < maxim[1].second))
                { maxim[1] = maxim[0]; }
        }
        
        if (maxim[1].second <= limita) { rezultat = maxim[1].first - limita * termen; stanga = termen + 1; }
        else { dreapta = termen - 1; }
    }

    cout << rezultat;
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29