Submission #1285717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285717		WH8	K blocks (IZhO14_blocks)	C++20	100 / 100	183 ms	81388 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double
#define sz(x) static_cast<int>((x).size())


signed main(){
	int n,k;cin>>n>>k;
	vector<int> v(n+1, 0);
	for(int i=1;i<=n;i++)cin>>v[i];
	vector<vector<int>> mem(k+1, vector<int>(n+1, 1e15));
	mem[0][0]=0;
	for(int i=1;i<=k;i++){
		stack<tuple<int,int,int>> st;
		st.push({0, 1e15, mem[i-1][0]});
		for(int j=1;j<=n;j++){
			int mn=mem[i-1][j-1];
			while(!st.empty() and get<0>(st.top()) <= v[j]){
				mn=min(mn, get<2>(st.top()));
				st.pop();
			}
			st.push({v[j], 
					min((st.empty()?(int)1e15:get<1>(st.top())),mn+v[j]), 
					mn});
			if(j >= i)mem[i][j]=get<1>(st.top());
		}
	}
	//~ for(int i=0;i<=k;i++){
		//~ for(int j=0;j<=n;j++){
			//~ cout<<mem[i][j]<<" ";
		//~ }
		//~ cout<<endl;
	//~ }
	cout<<mem[k][n];
}
/*
3 3
3 2 1


*/

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