Submission #1285285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285285		Jawad_Akbar_JJ	K blocks (IZhO14_blocks)	C++20	53 / 100	1097 ms	47200 KiB

blocks

#include <iostream>
#include <set>
#include <vector>

using namespace std;
const int N = 1<<17;
int dp[N][102], a[N], ft[N], prv[N];
vector<int> vec[N], v1, v2;

void Add(int i, int vl){
	for (;i; i -= i & -i)
		ft[i] = min(ft[i], vl);
}

int get(int i, int ans = 1e9){
	for (;i<N;i += i & -i)
		ans = min(ans, ft[i]);
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
	int n, k;
	cin>>n>>k;

	for (int i=1, mx = 0;i<=n;i++){
		cin>>a[i];
		mx = max(mx, a[i]);
		
		dp[i][1] = mx;
		for (int j=2;j<=k;j++)
			dp[i][j] = 1e9;

		while (v1.size() > 0 and a[i] > a[v1.back()])
			vec[i].push_back(v1.back()), v1.pop_back();
		v1.push_back(i);
	}

	for (int i=n;i>=1;i--){
		while (v2.size() > 0 and a[i] > a[v2.back()])
			prv[v2.back()] = i, v2.pop_back();
		v2.push_back(i), prv[i] = 1;
	}

	for (int j=2;j<=k;j++){
		for (int i=1;i<N;i++)
			ft[i] = 1e9;

		multiset<int> st;
		for (int i=1;i<=n;i++){
			for (int l : vec[i])
				st.erase(st.find(dp[l][j]));

			dp[i][j] = get(prv[i]) + a[i];
			if (st.size() > 0)
				dp[i][j] = min(dp[i][j], *begin(st));

			st.insert(dp[i][j]);
			Add(i, dp[i][j-1]);
		}
	}

	cout<<dp[n][k]<<'\n';
}

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