Submission #49654

#	Time	Username	Problem	Language	Result	Execution time	Memory
49654		khsoo01	Bali Sculptures (APIO15_sculpture)	C++11	100 / 100	155 ms	2540 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = (1ll<<50) - 1, N1 = 2005, N2 = 305;

ll n, s, e, a[N1], dt1[N1], dt2[N2][N2];

bool can1 (ll V) {
	for(ll i=1;i<=n;i++) {
		ll C = 0;
		dt1[i] = inf;
		for(ll j=i;j--;) {
			C += a[j+1];
			if((C & V) == C) {
				dt1[i] = min(dt1[i], dt1[j]+1);
			}
		}
	}
	return dt1[n] <= e;
}

bool can2 (ll V) {
	dt2[0][0] = true;
	for(ll i=1;i<=n;i++) {
		for(ll k=1;k<=i;k++) {
			ll C = 0;
			dt2[i][k] = false;
			for(ll j=i;j--;) {
				C += a[j+1];
				if((C & V) == C) {
					dt2[i][k] |= dt2[j][k-1];
				}
			}
			if(i == n && s <= k && k <= e && dt2[i][k]) {
				return true;
			}
		}
	}
	return false;
}

bool can (ll V) {
	return s == 1 ? can1(V) : can2(V);
}

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:48:7: 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:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
   ~~~~~^~~~~~~~~~~~~~

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