제출 #312248

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
312248	2020-10-12 20:58:53	tevdore	K개의 묶음 (IZhO14_blocks)	C++14	100 / 100	389 ms	81400 KiB

blocks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int N = 1e5 + 10;
ll n, k, mn, m;
ll a[N], dp[N][101];
stack < pair < ll, ll > > s;
main() {
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) dp[i][1] = max(a[i], dp[i - 1][1]);
    for(int i = 2; i <= k; i++) {
        while(!s.empty()) s.pop();
        for(int j = i; j <= n; j++) {
            m = 1e18;
            mn = dp[j - 1][i - 1];
            while(!s.empty() && s.top().second <= a[j]) {
                mn = min(mn, s.top().first);
                s.pop();
            }
            if(!s.empty()) m = s.top().first + s.top().second;
            dp[j][i] = min(mn + a[j], m);
            if(s.empty() || m >= a[j] + mn) s.push({mn, a[j]});
        }
    }
    cout << dp[n][k] << "\n";
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 47 / 47