Submission #25242

#	Time	Username	Problem	Language	Result	Execution time	Memory
25242		khsoo01	Bali Sculptures (APIO15_sculpture)	C++11	100 / 100	149 ms	2140 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = (1ll<<50)-1;
ll n, s, e, a[2005], dt1[2005];
bool dt2[305][305];

bool can (ll V) {
	if(s == 1) {
		for(ll i=1;i<=n;i++) {
			ll cur = 0;
			dt1[i] = inf;
			for(ll j=i-1;j>=0;j--) {
				cur += a[j+1];
				if((cur & V) == cur) {
					dt1[i] = min(dt1[i], dt1[j]+1);
				}
			}
		}
		return dt1[n] <= e;
	}
	else {
		dt2[0][0] = true;
		for(ll i=1;i<=n;i++) {
			for(ll k=1;k<=i;k++) {
				ll cur = 0;
				dt2[i][k] = false;
				for(ll j=i-1;j>=0;j--) {
					cur += a[j+1];
					if((cur & V) == cur) {
						dt2[i][k] |= dt2[j][k-1];
					}
				}
				if(i == n && s <= k && k <= e && dt2[i][k]) return true;
			}
		}
		return false;
	}
}

int main()
{
	scanf("%lld%lld%lld",&n,&s,&e);
	for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
	ll S = 0, E = inf;
	while(S<E) {
		ll M = (S+E)/2;
		can(M) ? E = M : S = M+1;
	}
	printf("%lld\n",S);
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:43:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&n,&s,&e);
                                ^
sculpture.cpp:44:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(ll 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