oj.uz

Submission #168765

# Submission time Handle Problem Language Result Execution time Memory
168765 2019-12-16T04:52:14 Z NHDanDz K blocks (IZhO14_blocks) C++14
0 / 100
 40 ms 41476 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][nmax];
int 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, 0x3f, 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.empty() && a[S.top().S] <= a[j])
            {
                MIN = min(MIN , S.top().F);
                S.pop();
            }
            d[i][j] = min(d[i][!S.empty() ? S.top().S : 0] , MIN + a[j]);
            //cout << (S.size() ? S.top().S : 0) << " ";
            S.push({MIN , i});
        }
        //cout << endl;
    }
    cout << d[k][n];
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 41464 KB Output is correct
2 Correct 35 ms 41464 KB Output is correct
3 Correct 35 ms 41464 KB Output is correct
4 Correct 35 ms 41464 KB Output is correct
5 Correct 35 ms 41464 KB Output is correct
6 Correct 35 ms 41464 KB Output is correct
7 Correct 35 ms 41464 KB Output is correct
8 Correct 35 ms 41464 KB Output is correct
9 Correct 35 ms 41464 KB Output is correct
10 Correct 35 ms 41444 KB Output is correct
11 Correct 35 ms 41464 KB Output is correct
12 Correct 40 ms 41440 KB Output is correct
13 Incorrect 35 ms 41476 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 47.0

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