Submission #882874

#	Time	Username	Problem	Language	Result	Execution time	Memory
882874		OAleksa	Bali Sculptures (APIO15_sculpture)	C++14	50 / 100	79 ms	604 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 dp[maxn][2], 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];
   	int ans = (1ll << 41) - 1;
   	auto check = [&](int x) {
   		for (int i = 1;i <= n;i++)
   			dp[i][0] = dp[i][1] = inf;
   		//dp[i][0] <= dp[i][1]
   		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][0] = min(dp[i][0], dp[j - 1][0] + 1);
   					if (dp[j - 1][0] + 1 >= l && dp[j - 1][0] + 1 <= r)
   						dp[i][1] = min(dp[i][1], dp[j - 1][0] + 1);
   					if (dp[j - 1][1] + 1 >= l && dp[j - 1][1] + 1 <= r)
   						dp[i][1] = min(dp[i][1], dp[j - 1][1] + 1);
   				}
   			}
   		}
   		return dp[n][1] <= r && dp[n][1] >= l;
   	};
   	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: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 21 / 21
• Subtask 4: 0 / 25
• Subtask 5: 29 / 29