제출 #1279765

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279765		SSKMF	Stove (JOI18_stove)	C++20	100 / 100	17 ms	828 KiB

stove

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

int moment[100001];

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 >> moment[indice]; }
    
    int64_t stanga = 0 , dreapta = 1000000000000000 , rezultat = 0;
    while (stanga <= dreapta)
    {
        const int64_t termen = (stanga + dreapta) >> 1;
        pair <int64_t , int> minim = {-moment[1] + termen + 1 , 0};
        for (int capat = 1 ; capat <= lungime ; capat++)
        {
            const int64_t candidat = minim.first + moment[capat];
            minim = min(minim , {candidat - moment[capat + 1] + termen + 1 , minim.second + 1});
            if (capat == lungime) { 
                if (minim.second + 1 <= limita) { dreapta = termen - 1; rezultat = candidat - 1LL * limita * termen; }
                else { stanga = termen + 1; }
            }
        }
    }

    cout << rezultat;
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50