Submission #341427

#	Time	Username	Problem	Language	Result	Execution time	Memory
341427		tengiz05	K blocks (IZhO14_blocks)	C++17	0 / 100	1 ms	364 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
template<class T> bool chmin(T& a, const T& b) {return a>b? a=b, true:false;}
template<class T> bool chmax(T& a, const T& b) {return a<b? a=b, true:false;}
const int mod = 1e9+7, N = 1e5+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
int a[N], n, m, k;
int dp[N][105];
void solve(int test_case){
	int i, j;
	cin >> n >> k;
	for(i=1;i<=n;i++){
		cin >> a[i];
	}
	for(i=0;i<=n;i++)
		for(j=0;j<=k;j++)dp[i][j] = mod;
	dp[0][0] = 0;
	int mxx = 0;
	for(i=1;i<=n;i++){
		chmax(mxx, a[i]);
		dp[i][1] = mxx;
	}
	for(j=2;j<=k;j++){
		vector<pii> st;
		for(i=1;i<=n;i++){
			// st.first = last block maximum, st.second = its dp
			int opdp = dp[i-1][j-1];
			while(!st.empty() && st.back().ff < a[i]){
				chmin(opdp, st.back().ss);
				st.pop_back();
			}
			if(st.empty() || st.back().ss+st.back().ff > a[i]+opdp){
				st.push_back({a[i], opdp});
			}
			dp[i][j] = opdp + st.back().ff;
		}
	}
	cout << dp[n][k];
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int _T;
	cin >> _T;
	for(int T_CASE = 1; T_CASE <= _T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

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