제출 #1294134

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1294134		SSKMF	Feast (NOI19_feast)	C++20	100 / 100	81 ms	1580 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) >> 1;
        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