제출 #1198483

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198483		steve_csp	K blocks (IZhO14_blocks)	C++17	100 / 100	79 ms	1864 KiB

blocks

#include <bits/stdc++.h>
#define ll long long
#define memaybeo main
#define en "\n";
#define hackspeed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define dafug return 0;
#define fi first
#define se second
using namespace std;
const int mmb = 1e5 + 5,inf = 1e9+369;
int n,k,a[mmb],dp[mmb],lef[mmb];
pair<int,int>p[mmb];
signed main() 
{
    cin >> n >> k;
    for(int i=1;i<=n;++i) cin >> a[i],lef[i] = max(lef[i-1],a[i]);
    for(int j=2;j<=k;++j) 
	{
        int sz = 0;
        for(int i=1;i<=n;++i) 
		{
            int ans = j <= i ? lef[i-1] : inf;
            lef[i-1] = dp[i-1];
            while(sz and a[i] >= p[sz-1].fi) ans = min(ans,p[--sz].se);
            if(!sz or a[i] + ans < p[sz-1].fi + p[sz-1].se) p[sz++] = make_pair(a[i],ans);
			dp[i] = p[sz-1].fi + p[sz-1].se;
        }
        lef[n] = dp[n];
    }
    cout << lef[n];
    dafug
}

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