Submission #252012

#	Time	Username	Problem	Language	Result	Execution time	Memory
252012		AMO5	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	90 ms	512 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

const ll INF=LLONG_MAX;
const int mxn=2e3+3;
bool DEBUG=0;

ll a[mxn];
int n,A,B;
ll ans = (1ll<<43)-1;

bool works(ll val){
	bool dp[n+1][n+1];
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=B&&j<=i; j++){
			dp[i][j]=0;
			for(int k=i-1; k>=0; k--){
				if(((a[i]-a[k])|val)<=val&&dp[k][j-1]){
					dp[i][j]=1;
					break;
				}
			}
		}
	}
	for(int i=A; i<=B; i++){
		if(dp[n][i])return 1;
	}
	return 0;
}

bool works1(ll val){
	int dp[n+1];
	dp[0]=0;
	for(int i=1; i<=n; i++){
		dp[i]=B+1;
		for(int j=0; j<i; j++){
			if(((a[i]-a[j])|val)<=val&&dp[i]>dp[j]+1){
				dp[i]=dp[j]+1;
			}
		}
	}
	return dp[n]<=B;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	cin >> n >> A >> B;
	a[0]=0ll;
	for(int i=1; i<=n; i++){
		cin >> a[i];
		a[i]+=a[i-1];
	}
	if(A>1){
		for(int i=42; i>=0; i--){
			if(works(ans^(1ll<<i)))ans^=(1ll<<i);
		}
	}else{
		for(int i=42; i>=0; i--){
			if(works1(ans^(1ll<<i)))ans^=(1ll<<i);
		}
	}
	cout << ans << '\n';
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN

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