Submission #882878

#	Time	Username	Problem	Language	Result	Execution time	Memory
882878		OAleksa	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	68 ms	696 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
const int maxn = 2010;
const int inf = 1e15;
int a[maxn], l, r, n, p[maxn];
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
   	cin >> n >> l >> r;
   	for (int i = 1;i <= n;i++)
   		cin >> a[i];
		for (int i = 1;i <= n;i++)
			p[i] = p[i - 1] + a[i];
		if (l == 1) {
				int ans = (1ll << 41) - 1;
	   	auto check = [&](int x) {
	   		int dp[n + 1] = {0};
	   		for (int i = 1;i <= n;i++)
	   			dp[i] = inf;
	   		for (int i = 1;i <= n;i++) {
	   			for (int j = i;j >= 1;j--) {
	   				int sm = p[i] - p[j - 1];
	   				if ((x & sm) == sm) {
	   					dp[i] = min(dp[i], dp[j - 1] + 1);
	   				}
	   			}
	   		}
	   		return dp[n] <= r;
	   	};
	   	for (int i = 40;i >= 0;i--) {
	   		if (check(ans - (1ll << i))) 
	   			ans -= (1ll << i);
	   	}
	   	cout << ans;
		}
		else {
	   	int ans = (1ll << 41) - 1;
	   	auto check = [&](int x) {
	   		set<int> dp[n + 1];
	   		//dp[i][0] <= dp[i][1]
	   		dp[0].insert(0);
	   		for (int i = 1;i <= n;i++) {
	   			for (int j = i;j >= 1;j--) {
	   				int sm = p[i] - p[j - 1];
	   				if ((x & sm) == sm) {
	   					for (auto u : dp[j - 1]) {
	   						dp[i].insert(u + 1);
	   					}
	   				}
	   			}
	   		}
	   		int ok = 0;
	   		for (auto u : dp[n])
	   			ok |= (u >= l && u <= r);
	   		return ok;
	   	};
	   	for (int i = 40;i >= 0;i--) {
	   		if (check(ans - (1ll << i))) 
	   			ans -= (1ll << i);
	   	}
	   	cout << ans;
   	}
	}
	return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:17:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   17 |     for (int i = 1;i <= n;i++)
      |     ^~~
sculpture.cpp:19:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   19 |   for (int i = 1;i <= n;i++)
      |   ^~~

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