Submission #56518

#	Time	Username	Problem	Language	Result	Execution time	Memory
56518		leejseo	Bali Sculptures (APIO15_sculpture)	C++98	0 / 100	53 ms	63400 KiB

sculpture

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

#define UNDEF -1

int L[2001], N, A, B;
long long M[2001][2001];
long long D[2001][2001];

void input(){
	scanf("%d%d%d", &N, &A, &B);
	memset(M, -1, sizeof(M));
	memset(D, -1, sizeof(D));
	for (int i=1; i<=N; i++) scanf("%d", &L[i]);
	for (int i=1; i<=N; i++){
		M[i][i] = L[i];
		for (int j=i+1; j<=N; j++){
			M[i][j] = M[i][j-1] | L[j];
		}
	}
}

void DP(){
	for (int i=1; i<=N; i++){
		D[i][1] = M[1][i];
		for (int j=2; j<=i; j++){
			D[i][j] = D[i-1][j-1] + L[i];
			for (int k=1; k<i; k++){
				if (D[k][j-1] != UNDEF) D[i][j] = min(D[i][j], D[k][j-1] + M[k+1][i]);
			}
		}
	}
}

int main(void){
	input();
	DP();
	long long ans = (long long)1e15;
	for (int i=A; i<=B; i++) ans = min(ans, D[N][i]);
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'void input()':
sculpture.cpp:11:7: 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:14:32: 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", &L[i]);
                           ~~~~~^~~~~~~~~~~~~

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