Submission #392945

#	Time	Username	Problem	Language	Result	Execution time	Memory
392945		vanic	K blocks (IZhO14_blocks)	C++14	0 / 100	1 ms	336 KiB

blocks

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn=1e5+5, maxk=105, Log=17, pot=(1<<Log);
const int inf=1e9;

struct tournament{
	int t[pot*2];
	void update(int x, int val){
		t[x]=val;
		for(x/=2; x>0; x/=2){
			t[x]=max(t[x*2], t[x*2+1]);
		}
	}
	int query(int L, int D, int x, int l, int d){
		if(L>=l && D<=d){
			return t[x];
		}
		int lijeva=0, desna=0;
		if((L+D)/2>=l){
			lijeva=query(L, (L+D)/2, x*2, l, d);
		}
		if((L+D)/2+1<=d){
			desna=query((L+D)/2+1, D, x*2+1, l, d);
		}
		return max(lijeva, desna);
	}
};

int n, k;
int dp[maxk][maxn];
int a[maxn];
tournament T;

void rijesi(int ind, int l, int d, int optl, int optd){
	int pos=(l+d)/2;
	int opti, minsol=inf;
	int maksi=T.query(0, pot-1, 1, min(optd, pos), pos);
	for(int i=min(optd, pos)-1; i>=optl; i--){
		if(minsol>maksi+dp[ind-1][i]){
			minsol=maksi+dp[ind-1][i];
			opti=i;
		}
		maksi=max(maksi, a[i]);
	}
//	cout << pos << ' ' << minsol << endl;
	dp[ind][pos]=minsol;
	if(l+1==d){
		return;
	}
	rijesi(ind, l, pos, optl, opti+1);
	if(d-l>2){
		rijesi(ind, pos+1, d, opti, optd);
	}
}

int main(){
	scanf("%d%d", &n, &k);
	for(int i=0; i<n; i++){
		scanf("%d", a+i+1);
		T.update(i+1+pot, a[i+1]);
	}
	for(int i=1; i<n; i++){
		dp[0][i]=inf;
	}
	for(int i=1; i<=k; i++){
		rijesi(i, i, n+1, i-1, n+1);
	}
	printf("%d\n", dp[k][n]);
}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
blocks.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |   scanf("%d", a+i+1);
      |   ~~~~~^~~~~~~~~~~~~
blocks.cpp: In function 'void rijesi(int, int, int, int, int)':
blocks.cpp:56:8: warning: 'opti' may be used uninitialized in this function [-Wmaybe-uninitialized]
   56 |  rijesi(ind, l, pos, optl, opti+1);
      |  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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