Submission #114566

#	Time	Username	Problem	Language	Result	Execution time	Memory
114566		ioilolcom	K blocks (IZhO14_blocks)	C++14	53 / 100	1086 ms	158592 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long int ll;
const int N=1e5+7;
const int K=200;
int a[N];
int n;
const int m=20;
ll dp[N][K];
int st[N][m];
int v;
int query(int L,int R){
	int j = log2(R - L + 1);
	int ans = max(st[L][j], st[R - (1 << j)+1][j]);
	//cout<<L<<" "<<R<<" "<<j<<endl;
	return ans;
}
/*
   int query(int l,int r){
        int ans=0;
        for(int i=l; i<=r; i++) {
                ans=max(ans,a[i]);
        }
        return ans;
   }
 */
int  solve(int idx,int k){

	if(idx==n+1) {
		if(k==v+1) {
			return 0;
		}
		return 1e9;
	}
	if(dp[idx][k]!=-1) {
		return dp[idx][k];
	}
	int ans=1e9;
	for(int j=idx; j<=n; j++) {
		ans=min(ans,query(idx,j)+solve(j+1,k+1));
	}
	return dp[idx][k]=ans;
}
int main()
{

	ios_base:: sync_with_stdio(false); cin.tie(0);
	cin>>n>>v;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		st[i][0]=a[i];
	}
	for (int j = 1; j < m; j++) {
		for (int i = 1; i + (1 << j) <=n+1; i++) {
			st[i][j] = max(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);
		}
	}
/*
        for (int j = 1; j < m; j++) {
                for (int i = 1; i + (1 << j) <=n; i++) {
                        cout<<" starting at i "<<i<<" of length 2^"<<j<<" "<<st[i][j]<<endl;
                }
        }
 */
	//cout<<st[4][1]<<endl;
	memset(dp,-1,sizeof dp);
	ll ans=solve(1,1);

	cout<<ans<<endl;
	return 0;
}

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