Submission #26257

#	Time	Username	Problem	Language	Result	Execution time	Memory
26257		szawinis	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	96 ms	6140 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
const int N = 2001;
const long long INF = 1e18;

int n, a, b, p[N];
long long ans, sum[N], dp[N];
bool check[N][N];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> a >> b;
	for(int i = 1; i <= n; i++) cin >> p[i], sum[i] = sum[i-1] + p[i];
	if(a == 1) {
		for(int pw = log2(sum[n]); pw >= 0; pw--) {
			fill(dp+1, dp+n+1, INF);
			for(int i = 1; i <= n; i++) for(int j = 0; j < i; j++) {
				if(!(sum[i] - sum[j] & (ans | 1ll << pw))) dp[i] = min(dp[j] + 1, dp[i]); 
			}
			if(dp[n] <= b) ans |= 1ll << pw;
		}
	} else {
		for(int pw = log2(sum[n]); pw >= 0; pw--) {
			memset(check, 0, sizeof(check));
			check[0][0] = true;
			for(int k = 1; k <= b; k++) {
				for(int i = 1; i <= n; i++) for(int j = 0; j < i; j++) {
					if(!(sum[i] - sum[j] & (ans | 1ll << pw))) check[i][k] |= check[j][k-1];
				}
			}
			for(int k = a; k <= b; k++) if(check[n][k]) {
				ans |= 1ll << pw;
				break;
			}
		}
	}
	cout << (1ll << int(log2(sum[n])+1)) - 1 - ans;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:18:17: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
     if(!(sum[i] - sum[j] & (ans | 1ll << pw))) dp[i] = min(dp[j] + 1, dp[i]); 
                 ^
sculpture.cpp:28:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
      if(!(sum[i] - sum[j] & (ans | 1ll << pw))) check[i][k] |= check[j][k-1];
                  ^

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