제출 #1281609

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281609		SSKMF	K개의 묶음 (IZhO14_blocks)	C++20	100 / 100	111 ms	2180 KiB

blocks

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

int sir[100001] , minim[100001] , stiva[100001] , candidati[100001] , prefix[100001] , temporar[100001];

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

    int lungime , secvente;
    cin >> lungime >> secvente;

    for (int indice = 1 ; indice <= lungime ; indice++)
        { cin >> sir[indice]; minim[indice] = max(minim[indice - 1] , sir[indice]); }

    candidati[0] = prefix[0] = 1000000000;
    for (int inceput = 2 ; inceput <= secvente ; inceput++)
    {
        for (int capat = inceput ; capat <= lungime ; capat++)
        {
            int __minim = minim[capat - 1];
            while (stiva[0] && sir[stiva[stiva[0]]] <= sir[capat])
                { __minim = min(__minim , candidati[stiva[0]--]); }

            stiva[++stiva[0]] = capat;
            candidati[stiva[0]] = __minim;
            prefix[stiva[0]] = min(prefix[stiva[0] - 1] , candidati[stiva[0]] + sir[capat]);
            temporar[capat] = prefix[stiva[0]];
        }

        stiva[0] = 0;
        for (int capat = inceput ; capat <= lungime ; capat++)
            { minim[capat] = temporar[capat]; }
    }

    cout << minim[lungime];
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 47 / 47