#include <iostream>
#include <vector>
using namespace std;
//Subtask 1, 2, 3, 4: N <= 100
/*
For the worst beauty value, we want to first of all make the most significant bit as small as possible.
Loop through all the bits: log(max_N) = 32
Loop through all the positions: N = 100
Loop through all the previous choices: N = 100
Loop through all the choices of x (a<x<b)= 100
Grand total = 32e6 = 3e7 √
*/
long long pow2[35];
// arr size, limits on x, sculpture values
long long solve_1(long long N, long long A, long long B, vector<long long> Y)
{
// for(long long y:Y) cout << y << ' ';
// cout << '\n';
long long dp[N+1][B+1]; //is it possible to partition 1..i long longo j groups such that no group has value v & 1<<bit == 1
long long res = pow2[35] - 1, temp; //fix this number
long long curr_res = 0;
for(long long bit = 34; bit >= 0; bit--) //fix this number
{
// cout << "bit = " << bit << '\n';
for(long long i = 0; i <= N; i++) for(long long x = 0; x <= B; x++) dp[i][x] = 0;
res -= pow2[bit];
// cout << "res = " << res << '\n';
dp[0][0] = 1;
for(long long i = 1; i <= N; i++)
{
dp[i][1] = (Y[i] | res) <= res;
for(long long x = 2; x <= B; x++)
{
for(long long j = 0; j < i; j++)
{
if(((Y[i] - Y[j]) | res) > res) continue;
if(!dp[j][x-1]) continue;
// cout << i << ' ' << x << ' ' << j << ' ' << Y[i] - Y[j] << ' ' << res << '\n';
dp[i][x] |= dp[j][x-1];
}
}
}
// for(long long x = 1; x <= B; x++)
// {
// for(long long i = 1; i <= N; i++)
// {
// cout << dp[i][x] << ' ';
// }
// cout << '\n';
// }
temp = 0;
for(long long x = A; x <= B; x++) temp |= dp[N][x];
if(!temp) res += pow2[bit];
// cout << "______________________\n";
}
return res;
}
/*
-----------------------------------------------------
*/
//Subtask 3, 5: A = 1
/*
*/
long long solve_2(long long N, long long B, vector<long long> Y)
{
return 0;
}
int main()
{
pow2[0] = 1;
for(int i = 1; i < 35; i++) pow2[i] = pow2[i-1] * 2;
long long N, A, B;
cin >> N >> A >> B;
vector<long long> Y(N+1);
Y[0] = 0;
for(long long i = 1; i <= N; i++)
{
cin >> Y[i];
Y[i] += Y[i-1];
}
/*if(N <= 100)*/cout << solve_1(N, A, B, Y) << '\n';
//else cout << solve_2(N, B, Y) << '\n'; //A = 1
}
Compilation message
sculpture.cpp: In function 'long long int solve_1(long long int, long long int, long long int, std::vector<long long int>)':
sculpture.cpp:27:15: warning: unused variable 'curr_res' [-Wunused-variable]
27 | long long curr_res = 0;
| ^~~~~~~~
sculpture.cpp:26:28: warning: array subscript 35 is above array bounds of 'long long int [35]' [-Warray-bounds]
26 | long long res = pow2[35] - 1, temp; //fix this number
| ~~~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
