oj.uz

Submission #96019

# Submission time Handle Problem Language Result Execution time Memory
96019 2019-02-05T09:13:16 Z Kastanda K blocks (IZhO14_blocks) C++11
0 / 100
 26 ms 7032 KB 
#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 * 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] = INF;
        for (int i = 1; i <= n; i++)
        {
            while (A[stk[r]] <= A[i])
                Adder(stk[r - 1], stk[r], A[i] - A[stk[r]]), r --;
            stk[++ r] = i;
            Adder(i - 1, i, A[i]);
            dp[w][i] = Getter(0, i);
            Adder(i, i + 1, dp[!w][i]);
            if (i - 1 >= j)
                assert(dp[w][i - 1] <= dp[w][i]);
        }
    }
    return !printf("%d\n", dp[k & 1][n]);
}

Compilation message

blocks.cpp: In function 'int main()':
blocks.cpp:36: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:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3448 KB Output is correct
2 Correct 4 ms 3448 KB Output is correct
3 Correct 4 ms 3448 KB Output is correct
4 Correct 5 ms 3448 KB Output is correct
5 Correct 4 ms 3448 KB Output is correct
6 Correct 5 ms 3448 KB Output is correct
7 Correct 4 ms 3448 KB Output is correct
8 Runtime error 8 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3448 KB Output is correct
2 Correct 4 ms 3448 KB Output is correct
3 Correct 4 ms 3448 KB Output is correct
4 Correct 5 ms 3448 KB Output is correct
5 Correct 4 ms 3448 KB Output is correct
6 Correct 4 ms 3448 KB Output is correct
7 Correct 4 ms 3448 KB Output is correct
8 Runtime error 7 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 7032 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -