Submission #142751

#	Time	Username	Problem	Language	Result	Execution time	Memory
142751		socho	Bali Sculptures (APIO15_sculpture)	C++14	0 / 100	33 ms	31992 KiB

sculpture

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

long long n, a, b;
long long arr[2005];

long long dp[2005][2005];

long long pf[2005];

long long sum(int a, int b) {
	return pf[b] - pf[a-1];
}

long long solve(int items, int ranges) {
	
	if (dp[items][ranges] != -1) return dp[items][ranges];
	
	long long lowest = INT_MAX;
	for (long long i=1; i<items; i++) {
		// solve(i, ranges-1) ^ (sum(i+1, items))
		long long curr = solve(i, ranges-1) | sum(i+1, items);
		lowest = min(lowest, curr);
	}
	return dp[items][ranges] = lowest;
	
}

int main() {

	cin >> n >> a >> b;
	long long allow = b + 5;
	
	for (int i=0; i<2005; i++) {
		for (int j=0; j<2005; j++) {
			dp[i][j] = -1;
		}
	}
	
	for (int i=0; i<n; i++) {
		cin >> arr[i];
	}
	
	pf[0] = 0;
	for (int i=1; i<=n; i++) {
		pf[i] = pf[i-1] + arr[i-1];
	}
	
	int x = 0;
	for (int i=0; i<n; i++) {
		x = x + arr[i];
		dp[i+1][1] = x;
	}
	
	
	
	for (int i=0; i<allow; i++) {
		dp[0][i] = 0;
	}

	long long best = INT_MAX;
	
	for (int i=a; i<=b; i++) {
		best = min(best, solve(n, i));
	}
	
	cout << best << endl;
	
}

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