oj.uz

Submission #90667

# Submission time Handle Problem Language Result Execution time Memory
90667 2018-12-23T12:17:46 Z P1QG K blocks (IZhO14_blocks) C++11
0 / 100
 9 ms 4728 KB 
#include<bits/stdc++.h>
#define maxn 100005
using namespace std;

int n, k, a[maxn], F[maxn][105];

int main()
{
    //freopen("BLOCKS.inp","r",stdin);
    //freopen("BLOCKS.out","w",stdout);

    scanf("%d%d", &n, &k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d", &a[i]);
    }


    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=k;j++) F[i][j] = 1e9+9;
    }

    F[0][1] = 0;
    for(int i=1;i<=n;i++) F[i][1] = max(F[i-1][1], a[i]);

    for(int i=2;i<=k;i++)
    {
        stack< pair<int,int> > P;
        for(int j=i;j<=n;j++)
        {
            int cur = F[j-1][i-1];

            while(P.size() && a[P.top().second] <= a[j])
            {
                cur = min(cur, P.top().first);
                P.pop();
            }

            F[j][i] = min(cur + a[j], (P.size() == 0)?F[0][0]:F[P.top().second][i]);

            P.push( make_pair(cur, i));
        }
    }

    printf("%d", F[n][k]);
}

Compilation message

blocks.cpp: In function 'int main()':
blocks.cpp:12: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:15: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 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 448 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 2 ms 524 KB Output is correct
7 Correct 2 ms 540 KB Output is correct
8 Correct 3 ms 600 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 2 ms 616 KB Output is correct
11 Correct 2 ms 616 KB Output is correct
12 Correct 2 ms 616 KB Output is correct
13 Incorrect 2 ms 616 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 616 KB Output is correct
2 Correct 2 ms 616 KB Output is correct
3 Correct 2 ms 616 KB Output is correct
4 Correct 2 ms 616 KB Output is correct
5 Correct 2 ms 616 KB Output is correct
6 Correct 2 ms 740 KB Output is correct
7 Correct 2 ms 740 KB Output is correct
8 Correct 2 ms 740 KB Output is correct
9 Correct 2 ms 740 KB Output is correct
10 Correct 2 ms 740 KB Output is correct
11 Correct 2 ms 740 KB Output is correct
12 Correct 2 ms 748 KB Output is correct
13 Correct 2 ms 748 KB Output is correct
14 Incorrect 2 ms 748 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 4728 KB Output isn't correct
2 Halted 0 ms 0 KB -