Submission #678027

#	Time	Username	Problem	Language	Result	Execution time	Memory
678027		TS_2392	K개의 묶음 (IZhO14_blocks)	C++14	100 / 100	181 ms	41192 KiB

blocks

#include <bits/stdc++.h>
#define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define rall(x) (x).rbegin(), (x).rend()
#define all(x) (x).begin(), (x).end()
#define sqr(x) (x) * (x)

#define eb emplace_back
#define epl emplace

#define lwb lower_bound
#define upb upper_bound

#define mp make_pair
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef long double ldb;
typedef unsigned int uint;
typedef unsigned long long ull;

typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;

template<class T1, class T2> bool minimize(T1 &a, T2 b){
    return a > b ? a = b, true : false;
}
template<class T1, class T2> bool maximize(T1 &a, T2 b){
    return a < b ? a = b, true : false;
}
const int N = 1e5 + 1, K = 101, oo = 1e9 + 10;
int n, k, a[N], dp[K][N];
int main(){
    //SPEED;
    cin >> n >> k;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0;
    for (int i = 1; i <= n; ++i) dp[1][i] = max(dp[1][i - 1], a[i]);
    for(int i = 2; i <= k; ++i){
        stack<pii> stk;
        for(int j = i; j <= n; ++j){
            int MinPrevF = dp[i - 1][j - 1];
            while(!stk.empty() && a[stk.top().fi] <= a[j]){
                minimize(MinPrevF, stk.top().se);
                stk.pop();
            }
            dp[i][j] = min(dp[i][stk.empty() ? 0 : stk.top().fi], MinPrevF + a[j]);
            stk.push({j, MinPrevF});
        }
    }
    cout << dp[k][n];
    return 0;
}

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