oj.uz

답안 #168766

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
168766 2019-12-16T04:54:20 Z NHDanDz K개의 묶음 (IZhO14_blocks) C++14
0 / 100
 45 ms 41592 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() ? 0 : S.top().second] , 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

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 41464 KB Output is correct
2 Correct 40 ms 41592 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 41416 KB Output is correct
6 Correct 40 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 41 ms 41464 KB Output is correct
10 Correct 40 ms 41464 KB Output is correct
11 Correct 35 ms 41424 KB Output is correct
12 Correct 45 ms 41464 KB Output is correct
13 Incorrect 35 ms 41520 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 41464 KB Output is correct
2 Correct 34 ms 41464 KB Output is correct
3 Correct 35 ms 41472 KB Output is correct
4 Correct 35 ms 41464 KB Output is correct
5 Correct 35 ms 41464 KB Output is correct
6 Correct 38 ms 41380 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 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 41464 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 35 ms 41464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 36 ms 41464 KB Output isn't correct
2 Halted 0 ms 0 KB -