Submission #96020

#	Time	Username	Problem	Language	Result	Execution time	Memory
96020		Kastanda	K blocks (IZhO14_blocks)	C++11	100 / 100	118 ms	3064 KiB

blocks

#include<bits/stdc++.h>
#define lc (id << 1)
#define rc (id << 1 ^ 1)
#define md ((l + r) >> 1)
using namespace std;
const int N = 100005, K = 104, INF = 30000 * 10000;
int n, k, A[N], dp[2][N], stk[N];
int mn[N], pref[N];
/*int mn[N * 4], lazy[N * 4];
int le, ri, val;
void Add(int id = 1, int l = 0, int r = n + 1)
{
    if (ri <= l || r <= le)
        return ;
    if (le <= l && r <= ri)
    {
        lazy[id] += val;
        mn[id] += val;
        return ;
    }
    Add(lc, l, md);
    Add(rc, md, r);
    mn[id] = min(mn[lc], mn[rc]) + lazy[id];
}
int Get(int id = 1, int l = 0, int r = n + 1)
{
    if (ri <= l || r <= le)
        return (INF);
    if (le <= l && r <= ri)
        return (mn[id]);
    return (min(Get(lc, l, md), Get(rc, md, r)) + lazy[id]);
}
inline void Adder(int _le, int _ri, int _val) {le = _le; ri = _ri; val = _val; Add();}
inline int Getter(int _le, int _ri) {le = _le; ri = _ri; return (Get());}*/
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &A[i]);
        dp[0][i] = dp[1][i] = INF;
    }
    A[0] = dp[1][0] = INF;
    for (int j = 1; j <= k; j++)
    {
        int w = j & 1;
        int r = 1;
        memset(mn, 0, sizeof(mn));
        //memset(lazy, 0, sizeof(lazy));
        //Adder(0, 1, dp[!w][0]);
        dp[w][0] = pref[0] = mn[0] = INF;
        for (int i = 1; i <= n; i++)
        {
            mn[i] = dp[!w][i - 1] + A[i];
            while (A[stk[r]] <= A[i])
                mn[i] = min(mn[i], mn[stk[r]] + A[i] - A[stk[r]]), r --;
                //Adder(stk[r - 1], stk[r], A[i] - A[stk[r]]), r --;
            pref[i] = min(pref[stk[r]], mn[i]);
            stk[++ r] = i;
            dp[w][i] = pref[i];
            //Adder(i - 1, i, A[i]);
            //dp[w][i] = Getter(0, i);
            //Adder(i, i + 1, dp[!w][i]);
        }
    }
    return !printf("%d\n", dp[k & 1][n]);
}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~
blocks.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
         ~~~~~^~~~~~~~~~~~~

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