Submission #44999

#	Time	Username	Problem	Language	Result	Execution time	Memory
44999		Mamnoon_Siam	Bali Sculptures (APIO15_sculpture)	C++17	71 / 100	156 ms	4888 KiB

sculpture

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC optimize("unroll-loops")

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

#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'
#define int long long

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
    return os<<"(" <<p.first<<", "<<p.second<<")"; }

typedef pair<int, int> ii;
template<typename T> using min_pq =
	priority_queue<T, vector<T>, greater<T> >;

//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};

const int maxn = 2002;

int n, A, B;
int a[maxn];
bool dp[maxn][maxn];

int mask = (1LL << 40) - 1;

bool fek() {
	int temp[maxn];
	temp[0] = 0;
	for(int i=1; i<=n; i++) {
		temp[i] = 987654321;
		int s = 0;
		for(int j=i; j>=1; j--) {
			s += a[j];
			if((s & mask) == s) {
				temp[i] = min(temp[i], temp[j-1] + 1);
			}
		}
	} return temp[n] <= B;
}

bool can() {
	if(A == 1) return fek();
	MEMSET(dp, 0);
	dp[0][0] = 1;
	for(int k=1; k<=n; k++) {
		for(int i=1; i<=n; i++) {
			int s = 0;
			for(int j=i-1; j>=0; j--) {
				s += a[j+1];
				dp[k][i] |= ((s & mask) == s and dp[k-1][j]);
			}
		}
	}
	bool ret = false;
	for(int i=A; i<=B; i++) {
		ret |= dp[i][n];
	} return ret;
}

int32_t main () {
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	cin>>n>>A>>B;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
	}
	for(int i=39; i>=0; i--) {
		mask ^= (1LL << i);
		if(!can()) mask ^= (1LL << i);
	}
	cout << mask << endl;
	return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'long long int myrand(long long int, long long int)':
sculpture.cpp:17:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
  ^~
sculpture.cpp:17:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
                          ^~~

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