Submission #767223

#	Time	Username	Problem	Language	Result	Execution time	Memory
767223		KN200711	K blocks (IZhO14_blocks)	C++14	0 / 100	1 ms	340 KiB

blocks

# include <bits/stdc++.h>
using namespace std;

int arr[100001];
int dp[101][100001], opt[101][100001];
int sparse[18][100001];

int cost(int a, int b) {
	int x = b - a + 1;
	int v = 0;
	for(int i=17;i>=0;i--) {
		if(x&(1 << i)) {
			v = max(v, sparse[i][a]);
			a += (1 << i);
		}
	}
	return v;
}

int main() {
	int N, K;
	scanf("%d %d", &N, &K);
	
	for(int i=1;i<=N;i++) {
		scanf("%d", &arr[i]);
	}
	
	for(int i=0;i<=17;i++) {
		for(int k=1;k<=N;k++) {
			if(i == 0) sparse[i][k] = arr[k];
			else sparse[i][k] = max(sparse[i-1][k], sparse[i-1][(k + (1 << (i - 1)) - 1)%N + 1]);
		}
	}
	
//	cout<<cost(2, 3)<<endl;
	
	int sum = 0;
	for(int i=0;i<=N;i++) opt[K + 1][i] = i;
	
	for(int i=0;i <= N;i++) {
		for(int k=1;k+i <= N && k <= K; k++) {
			
			if(i == 0) {
				sum += arr[k];
				dp[k][k + i] = sum;
				opt[k][k + i] = k + i;
			} else {
				// (i, k-1) <= (i, k) <= (i + 1, k)
				int l = k + i;
				int optVal = 1e9, optIdx = -1;
				for(int p = opt[k][l - 1]; p <= opt[k + 1][l];p ++) {
				//	if(k == 2 && l == 3) cout<<"p : "<<opt[k][l-1]<<" "<<p<<endl;
					int val = dp[k - 1][p - 1] + cost(p, l);
					if(val < optVal) {
						optVal = val;
						optIdx = p;
					}
				}
				dp[k][l] = optVal;
				opt[k][l] = optIdx;
			}
		//	cout<<k<<" "<<k+i<<" "<<dp[k][k+i]<<endl;
		}
	}
	printf("%d\n", dp[K][N]);
}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  scanf("%d %d", &N, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~~
blocks.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%d", &arr[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

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