oj.uz

Submission #142751

# Submission time Handle Problem Language Result Execution time Memory
142751 2019-08-10T17:01:12 Z socho Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 33 ms 31992 KB 
#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.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 29.0

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