Submission #761285

#	Time	Username	Problem	Language	Result	Execution time	Memory
761285		KN200711	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	102 ms	352 KiB

sculpture

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

int N, A, B;
ll arr[2001];
int mn[2001];

bool fn(ll a) {
	for(int i=1;i<=N;i++) mn[i] = 1e9;
	mn[0] = 0;
	for(int i=1;i<=N;i++) {
		ll ad = 0ll;
		for(int k=i-1;k>=0;k--) {
			ad += arr[k + 1];
			if((ad|a) == a) {
				if(mn[k] != 1e9) mn[i] = min(mn[i], mn[k] + 1);
			}
		}
	}
	if(mn[N] <= B) return 1;
	return 0;
}

void solve() {
	ll ls = (1ll << 62) - 1ll;
	for(int i=61;i>=0;i--) {
		ll P = ls - (1ll << i);
		if(fn(P)) {
			ls = P;
		}
	}
	printf("%lld\n", ls);
}

bool dp[201][201];

bool cek(ll P) {
	for(int c=0;c<=200;c++) {
		for(int d=0;d<=200;d++) {
			dp[c][d] = 0;
		}
	}
	dp[0][0] = 1;
	for(int k=1;k<=N;k++) {
		ll ad = 0ll;
		for(int c=k-1;c>=0;c--) {
			ad += arr[c + 1];
			if((ad|P) == P) {
				for(int l=0;l<B;l++) {
					if(dp[c][l]) dp[k][l+1] = 1;
				}
			}
		}
	}
	for(int i=A;i<=B;i++) {
		if(dp[N][i]) return 1;
	}
	return 0;
}

void ans() {
	ll ls = (1ll << 62) - 1ll;
	for(int i=61;i>=0;i--) {
		// cek bit ini bisa atau ngga
		ll P = ls - (1ll << i);
		if(cek(P)) {
			ls = P;
		}
	}
	printf("%lld\n", ls);
}

int main() {
	scanf("%d %d %d", &N, &A, &B);
	for(int i=1;i<=N;i++) scanf("%lld", &arr[i]);
	
	if(A == 1) solve();
	else ans();
	
//	cout<<cek(9)<<endl;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  scanf("%d %d %d", &N, &A, &B);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:76:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  for(int i=1;i<=N;i++) scanf("%lld", &arr[i]);
      |                        ~~~~~^~~~~~~~~~~~~~~~~

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