Submission #1125316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125316		Tsagana	K blocks (IZhO14_blocks)	C++17	100 / 100	99 ms	4352 KiB

blocks

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

/*
     /\_/\
    (= ._.)
    / >?  \>!
*/

int n, s;
int a[100001];
int l[100001];
int mn[100001];
int dp[100001][2];

void prep() {
	cin >> n >> s;
    for (int i = 1; i <= n; i++) cin >> a[i]; 
    for (int i = 1; i <= n; i++)
    for (l[i] = i-1; l[i] > 0 && a[l[i]] <= a[i];) l[i] = l[l[i]]; 
    
    memset(dp, 0x3f, sizeof dp);
	dp[1][1] = a[1];
    for (int i = 2; i <= n; i++) dp[i][1] = max(dp[i-1][1], a[i]);
}
void solve () {
	prep();
	for (int k = 2; k <= s; k++) {  
        mn[k-1] = dp[0][0];
        for (int i = 1; i <= n; i++) dp[i][k&1] = dp[0][0];
        for (int i = k; i <= n; i++) {
            mn[i] = dp[i-1][(k-1)&1];
            for (int j = i - 1; j > l[i]; j = l[j]) mn[i] = min(mn[i], mn[j]);
            dp[i][k&1] = min(dp[l[i]][k&1], mn[i] + a[i]);
        }
    }
    cout << dp[n][s&1];
}
signed main() {IOS solve(); return 0;}

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