Submission #1071619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071619		Muhammet	Bali Sculptures (APIO15_sculpture)	C++17	46 / 100	21 ms	604 KiB

sculpture

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

#define int long long
#define sz(x) (int)x.size()
#define ff first
#define ss second

const int N = 3005;
const int M = 1e9 + 7;

int T, n, c[N], a, b;

signed main(){
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n >> a >> b;
	vector <int> p(n+1,0);
	for(int i = 1; i <= n; i++){
		cin >> c[i];
		p[i] = p[i-1] + c[i];
	}

	int s = 0, ans = 1e18;
	for(int i = 1; i <= n; i++){
		s += c[i];
		vector <vector <int>> dp(n+1, vector <int> (n+2,1e18));
		for(int j = i+1; j <= n; j++){
			dp[j][1] = (p[j]-p[i])|s;
			for(int j1 = j-1; j1 > i; j1--){
				for(int ste = 1; ste <= n; ste++){
					dp[j][ste+1] = min(dp[j][ste+1],(dp[j1][ste]|(p[j]-p[j1]))|s);
				}
			}
		}
		dp[n][1] = (p[n]-p[i])|s;
		for(int j = a-1; j < b; j++){
			ans = min(ans,dp[n][j]);
		}
	}
	if(a == 1) ans = min(ans,p[n]);
	cout << ans << "\n";

	return 0;
}
// 6 1 3
// 8 1 2 1 5 4

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