Submission #572623

#	Time	Username	Problem	Language	Result	Execution time	Memory
572623		beaconmc	Bali Sculptures (APIO15_sculpture)	C++14	0 / 100	1 ms	340 KiB

sculpture

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
typedef long long ll;

#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
#define double long double

using namespace std;

ll n,a,b;
ll nums[2005];
ll dp1[2005];
ll dp2[2005][2005];


ll poww(ll n){
	ll sus = 1;

	FOR(i,0,n){
		sus *= 2;
	}
	return sus;
}
int check(ll v){
	FOR(i,0,n+2) FOR(j,0,n+2) dp2[i][j] = 100;

	FOR(i,0,n+1) dp1[i] = 100;

	dp1[0] = 0;

	if (a==1){
		FOR(i,0,n+1){
			ll cur = 0;
			FOR(x, i+1, n+1){
				cur += nums[x];
				if ((cur&v)==cur) dp1[x] = min(dp1[x], dp1[i] | cur);
			}
		}
		if ((dp1[n]&v)==dp1[n]) return 1;
		return 0;
	}else{
		dp2[0][0] = 0;

		FOR(i,0,n+1){
			FOR(j,0,n+1){
				ll cur = 0;
				FOR(x, i+1, n+1){
					cur += nums[x];
					if ((cur&v)==cur) dp2[x][j+1] = min(dp2[x][j+1], dp2[i][j] | cur);
				}
			}
		}


		FOR(i,a,b+1){
			if ((dp2[n][i]&v) == dp2[n][i]) return 1;
		}
	}


	return 0;

}


int main(){
	cin >> n >> a >> b;
	FOR(i,0,n) cin >> nums[i+1];

	ll sus = (1<<31)-1;

	FORNEG(i, 30, -1){
		sus -= poww(i);
		if (check(sus)) continue;
		else sus += poww(i);
	}
	cout << sus;

}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:71:18: warning: integer overflow in expression of type 'int' results in '2147483647' [-Woverflow]
   71 |  ll sus = (1<<31)-1;
      |           ~~~~~~~^~

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