oj.uz

Submission #168761

# Submission time Handle Problem Language Result Execution time Memory
168761 2019-12-16T04:44:46 Z NHDanDz K blocks (IZhO14_blocks) C++14
0 / 100
 84 ms 82680 KB 
/// NHDanDz
#include <bits/stdc++.h>
#define nmax 100005
#define F first
#define S second
#define PB push_back
#define PF push_front
#define ll long long
#define int ll
#define RyoLoveHentai "blocks"
#define pii pair<int,int>
#define reset(a) memset(a,0,sizeof(a))
using namespace std;
int n , k , a[nmax] , d[105][100005];
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    memset(d , 19 , sizeof(d));
    d[1][0] = 0;
    for(int i = 1; i <= n ; i++)
        d[1][i] = max(d[1][i - 1] , a[i]);
    for(int i = 2; i <= k; i++)
    {
        stack <pii> S;
        for(int j = i; j <= n; j++)
        {
            int MIN = d[i - 1][j - 1];
            //cout << MIN << " ";
            while(S.size() && a[S.top().S] <= a[j])
            {
                MIN = min(MIN , S.top().F);
                S.pop();
            }
            d[i][j] = min(d[i][S.size() ? S.top().S : 0] , MIN + a[j]);
            //cout << (S.size() ? S.top().S : 0) << " ";
            S.push({MIN , i});
        }
        //cout << endl;
    }
    cout << d[k][n];
}

Compilation message

blocks.cpp:15:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 82552 KB Output is correct
2 Correct 67 ms 82620 KB Output is correct
3 Correct 67 ms 82552 KB Output is correct
4 Correct 67 ms 82552 KB Output is correct
5 Correct 67 ms 82524 KB Output is correct
6 Correct 67 ms 82552 KB Output is correct
7 Correct 67 ms 82556 KB Output is correct
8 Correct 67 ms 82528 KB Output is correct
9 Correct 67 ms 82552 KB Output is correct
10 Correct 76 ms 82552 KB Output is correct
11 Correct 79 ms 82552 KB Output is correct
12 Correct 77 ms 82552 KB Output is correct
13 Incorrect 77 ms 82552 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 82552 KB Output is correct
2 Correct 77 ms 82552 KB Output is correct
3 Correct 77 ms 82552 KB Output is correct
4 Correct 84 ms 82552 KB Output is correct
5 Correct 72 ms 82552 KB Output is correct
6 Correct 71 ms 82680 KB Output is correct
7 Correct 76 ms 82552 KB Output is correct
8 Correct 68 ms 82552 KB Output is correct
9 Correct 68 ms 82680 KB Output is correct
10 Correct 79 ms 82504 KB Output is correct
11 Correct 76 ms 82552 KB Output is correct
12 Correct 67 ms 82548 KB Output is correct
13 Correct 74 ms 82500 KB Output is correct
14 Incorrect 73 ms 82680 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

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

Subtask #4
0 / 47.0

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