제출 #31128

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31128		nibnalin	Bali Sculptures (APIO15_sculpture)	C++14	0 / 100	0 ms	17728 KiB

sculpture

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int maxn = int(2e3)+5, inf = int(1e9)+5;

int A[maxn], dp[maxn][maxn];

int compute(int idx, int k, int l, int r)
{
	pair<int, int> res = {inf, -1};
	for(int i = max(idx+1, l);i <= r;i++)
	{
		int c = dp[k-1][i]|(A[i-1]-A[idx-1]);
		//cout << idx << " " << i << " " << c << "\n";
		if(c < res.first) res = {c, i};
	}
	dp[k][idx] = res.first;
	return res.second;
}

void solve(int L, int R, int optL, int optR, int k)
{
	int mid = (L+R)/2;
	int loc = compute(mid, k, optL, optR);
	if(mid < R) solve(mid+1, R, loc, optR, k);
	if(L < mid) solve(L, mid-1, optL, loc, k);
}

int main(void)
{
	int n, a, b;
	scanf("%d%d%d", &n, &a, &b);
	for(int i = 1;i <= n;i++) scanf("%d", &A[i]);
	for(int i = 1;i <= n;i++) A[i] += A[i-1];

	for(int i = 1;i <= n;i++) dp[1][i] = A[n]-A[i-1];

	for(int i = 2;i <= b;i++) solve(1, n, 1, n, i);
	printf("%d\n", dp[b][1]);
}

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

sculpture.cpp: In function 'int main()':
sculpture.cpp:34:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &a, &b);
                             ^
sculpture.cpp:35:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1;i <= n;i++) scanf("%d", &A[i]);
                                              ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 25
• Subtask 5: 0 / 29