Submission #469913

#	Time	Username	Problem	Language	Result	Execution time	Memory
469913		iulia13	K blocks (IZhO14_blocks)	C++14	100 / 100	195 ms	41008 KiB

blocks

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
const int LVL = 105;
const int INF = 1e9 + 5;
int a[N];
int dp[LVL][N];
int sol[N];
int st[N];
int main()
{
    int n, i, K;
    cin >> n >> K;
    for (i = 1; i <= n; i++)
    {
        cin >> a[i];
        dp[1][i] = max(dp[1][i - 1], a[i]);
    }
    for (i = 1; i <= K; i++)
        dp[i][0] = INF;
    for (int lvl = 2; lvl <= K; lvl++)
    {
        int k = 0;
        for (i = 1; i <= n; i++)
        {
            int ans = dp[lvl - 1][i - 1]; ///a[i] singur
            while (k && a[st[k]] <= a[i]) /// [.......][....st[k]]...i]
            {
                ans = min(ans, sol[st[k]]);
                k--;
            }
            sol[i] = ans;
            dp[lvl][i] = a[i] + ans;
            if (k)
                dp[lvl][i] = min(dp[lvl][i], dp[lvl][st[k]]);
            st[++k] = i;
        }
    }
    cout << dp[K][n];
    return 0;
}

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