Submission #404104

#	Time	Username	Problem	Language	Result	Execution time	Memory
404104		ritul_kr_singh	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	136 ms	452 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

const int MAXN = 2000;

int n, a, b, y[MAXN + 1] = {0};

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> a >> b;
	for(int i=1; i<=n; ++i) cin >> y[i], y[i] += y[i-1];

	int bad = 0, ans = 0;

	for(int m=43; m>=0; --m){
		bad |= 1LL << m;
		if(a < 2){
			int dp[n+1] = {0};
			for(int i=1; i<=n; ++i){
				dp[i] = n + 1;
				for(int j=0; j<i; ++j){
					if(!(bad & (y[i]-y[j]))) dp[i] = min(dp[i], dp[j] + 1);
				}
			}
			if(dp[n] > b) bad ^= 1LL << m, ans ^= 1LL << m;
		}else{
			bool dp[n+1][n+1];
			for(int i=0; i<=n; ++i) fill(dp[i], dp[i]+n+1, 0);
			dp[0][0] = 1;
			for(int i=1; i<=n; ++i){
				for(int j=0; j<i; ++j){
					if(bad & (y[i]-y[j])) continue;
					for(int k=1; k<=n; ++k)	dp[i][k] = dp[i][k] || dp[j][k-1];
				}
			}
			bool ok = false;
			for(int i=a; i<=b; ++i) ok = ok || dp[n][i];
			if(!ok) bad ^= 1LL << m, ans ^= 1LL << m;
		}
	}
	cout << ans;
}

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