oj.uz

Submission #392944

# Submission time Handle Problem Language Result Execution time Memory
392944 2021-04-22T11:22:31 Z vanic K blocks (IZhO14_blocks) C++14
0 / 100
 1 ms 332 KB 
#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[i][0]=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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -