Submission #316819

#	Time	Username	Problem	Language	Result	Execution time	Memory
316819		parsabahrami	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	81 ms	512 KiB

sculpture

//! Starman - Dawid Bowie
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;
 
#define sz(x)                       (ll) x.size()
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second

ll Pow(ll a, ll b, ll md, ll ans = 1) {
    for (; b; b >>= 1, a = a * a % md)
        if (b & 1)
            ans = ans * a % md;
    return ans % md;
}
const ll MAXN = 2e3 + 10;
const ll INF  = 8e18;
const ll MOD  = 1e9 + 7;
int pd[110][110], dp[MAXN], n, a, b;
ll A[MAXN];

int check(ll x) {
	fill(dp, dp + MAXN, MOD);
	dp[0] = 0;
	for (int i = 0; i < n; i++) {
		ll sum = 0;
		for (int k = i + 1; k <= n; k++) {
			sum += A[k];
			if ((sum | x) == x) dp[k] = min(dp[i] + 1, dp[k]);
		}
	}
	return dp[n] <= b;
}

ll chk(ll x) {
	memset(pd, 0, sizeof pd);
	pd[0][0] = 1;
	for (ll i = 0; i < n; i++) {
		for (ll j = 0; j < b; j++) {
			ll sum = 0;
			for (ll k = i + 1; k <= n; k++) {
				sum += A[k];
				if ((sum | x) == x) pd[k][j + 1] |= pd[i][j];
			}
		}
	}
	for (ll i = a; i <= b; i++) {
		if (pd[n][i]) return 1;
	}
	return 0;
}

void sub() {
	ll ans = (1LL << 45) - 1;
	for (ll i = 44; ~i; i--) {
		ans -= (1LL << i);
		if (chk(ans) == 0) ans += (1LL << i);
	}
	printf("%lld\n", ans);
}

int main() {
	scanf("%d%d%d", &n, &a, &b);
	for (int i = 1; i <= n; i++) scanf("%lld", &A[i]);
		if (a != 1) {
		sub();
		return 0;
	}
	ll ans = (1LL << 44) - 1;
	for (int i = 43; ~i; i--) {
		ans ^= (1LL << i);
		if (check(ans) == 0) ans |= (1LL << i);
	}
	printf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |  scanf("%d%d%d", &n, &a, &b);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:70:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |  for (int i = 1; i <= n; i++) scanf("%lld", &A[i]);
      |                               ~~~~~^~~~~~~~~~~~~~~

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