#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll subtask1(int n, int l, int r, vector <int> a)
{
ll ans = (1LL << 60);
for (int mask = 1; mask < (1 << n); mask += 2)
{
int bits = 0, aux = mask;
while (aux)
{
bits++;
aux -= aux & (-aux);
}
if (l <= bits && bits <= r)
{
ll curs = 0, cur = 0;
for (int i = 0; i < n; i++)
{
if (mask & (1 << i))
{
cur |= curs;
curs = 0;
}
curs += a[i];
}
cur |= curs;
ans = min(ans, cur);
}
}
return ans;
}
ll subtask2(int n, int l, int r, vector <int> a)
{
const int N = 50 + 1;
const int L = 20 + 1;
const int SM = 512 + 1;
bool okoq[N][L][SM];
for (int i = 0; i < N; i++)
for (int j = 0; j < L; j++)
for (int k = 0; k < SM; k++)
okoq[i][j][k] = 0;
okoq[0][0][0] = 1;
for (int i = 0; i < n; i++)
for (int cnt = 0; cnt < r; cnt++)
for (int x = 0; x < SM; x++)
if (okoq[i][cnt][x])
{
int val = 0;
for (int j = i + 1; j <= n; j++)
{
val += a[j - 1];
okoq[j][cnt + 1][x | val] = 1;
}
}
int mn = 10000;
for (int c = l; c <= r; c++)
for (int x = 0; x < SM; x++)
if (okoq[n][c][x])
mn = min(mn, x);
return mn;
}
bool okoq[101][101][2048];
ll subtask3(int n, int l, int r, vector <int> a)
{
for (int i = 0; i <= 100; i++)
for (int j = 0; j <= 100; j++)
for (int k = 0; k < 2048; k++)
okoq[i][j][k] = 0;
okoq[0][0][0] = 1;
for (int i = 0; i < n; i++)
for (int cnt = 0; cnt < r; cnt++)
for (int x = 0; x < 2048; x++)
if (okoq[i][cnt][x])
{
int val = 0;
for (int j = i + 1; j <= n; j++)
{
val += a[j - 1];
okoq[j][cnt + 1][x | val] = 1;
}
}
int mn = 10000;
for (int c = l; c <= r; c++)
for (int x = 0; x < 2048; x++)
if (okoq[n][c][x])
mn = min(mn, x);
return mn;
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
/// freopen ("input", "r", stdin);
int n, l, r;
cin >> n >> l >> r;
vector <int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
if (n <= 100 && *max_element(a.begin(), a.end()) <= 20)
{
cout << "Subtask 3\n";
cout << subtask3(n, l, r, a) << "\n";
return 0;
}
if (n <= 20)
{
cout << subtask1(n, l, r, a) << "\n";
return 0;
}
if (n <= 50 && l <= 20 && r <= 20 && *max_element(a.begin(), a.end()) <= 10)
{
cout << subtask2(n, l, r, a) << "\n";
return 0;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
27 ms |
20728 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
27 ms |
20728 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
28 ms |
20732 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
30 ms |
20856 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
39 ms |
20704 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |