제출 #767734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
767734		KN200711	K개의 묶음 (IZhO14_blocks)	C++14	0 / 100	1 ms	340 KiB

blocks

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

int arr[100001];
int dp[102][100001], opt[102][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, mx = 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 if(k == 1) {
				mx = max(mx, arr[k + i]);
				dp[k][k + i] = mx;
				opt[k][k + i] = 1;
			} else {
				// (i, k-1) <= (i, k) <= (i + 1, k)
				int l = k + i;
				int optVal = 1e9, optIdx = -1;
				for(int p = max(opt[k][l - 1], k); 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]);
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 18
• Subtask 3: 0 / 21
• Subtask 4: 0 / 47