# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
108832 | kuroni | Bali Sculptures (APIO15_sculpture) | C++17 | 96 ms | 640 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 2005;
int n, a, b, f[N];
bool chk[N][N];
long long s[N];
bool subtask_4(long long lim)
{
chk[0][0] = true;
for (int i = 1; i <= n; i++)
{
fill(chk[i], chk[i] + b + 1, false);
for (int j = 1; j <= i; j++)
if (((s[i] - s[j - 1]) & lim) == (s[i] - s[j - 1]))
for (int k = 1; k <= b; k++)
chk[i][k] |= chk[j - 1][k - 1];
}
for (int i = a; i <= b; i++)
if (chk[n][i])
return true;
return false;
}
bool subtask_5(long long lim)
{
f[0] = 0;
for (int i = 1; i <= n; i++)
{
f[i] = b + 1;
for (int j = 1; j <= i; j++)
if (((s[i] - s[j - 1]) & lim) == (s[i] - s[j - 1]))
f[i] = min(f[i], f[j - 1] + 1);
}
return f[n] <= b;
}
int main()
{
scanf("%d%d%d", &n, &a, &b);
for (int i = 1; i <= n; i++)
{
scanf("%lld", s + i);
s[i] += s[i - 1];
}
long long ans = (1LL << 41) - 1;
for (int i = 40; i >= 0; i--)
if (n <= 100)
{
if (subtask_4(ans ^ (1LL << i)))
ans ^= (1LL << i);
}
else
{
if (subtask_5(ans ^ (1LL << i)))
ans ^= (1LL << i);
}
printf("%lld", ans);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |