oj.uz

Submission #767225

# Submission time Handle Problem Language Result Execution time Memory
767225 2023-06-26T14:19:51 Z KN200711 K blocks (IZhO14_blocks) C++14
0 / 100
 1 ms 340 KB 
# 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) {
	if(a > b) return 1e9;
	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 - 1;
			} 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] + cost(p + 1, 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

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

Subtask #1
0 / 14.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 340 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 340 KB Output is correct
2 Incorrect 0 ms 340 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 340 KB Output is correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -