# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
33728 | sinhriv | Bali Sculptures (APIO15_sculpture) | C++14 | 46 ms | 2016 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 <bits/stdc++.h>
using namespace std;
const int N = 130;
int n, a, b;
int f[N];
int arr[N];
long long sum[N];
void small(){
long long ans = sum[n];
for(int mask = 0; mask < (1 << (n - 1)); ++mask){
int cnt = __builtin_popcount(mask) + 1;
if(cnt < a || cnt > b) continue;
long long curr = 0, now = 0;
for(int i = 1; i <= n; ++i){
curr += arr[i];
if(mask & (1 << (i - 1))){
now |= curr;
curr = 0;
}
}
now |= curr;
ans = min(ans, now);
}
cout << ans;
}
void Medium(){
for(int value = 0; value < (1 << 11); ++value){
memset(f, 60, sizeof f);
f[0] = 0;
for(int i = 1; i <= n; ++i){
for(int j = i - 1; j >= 0; --j){
if((value | (sum[i] - sum[j])) == value){
f[i] = min(f[i], f[j] + 1);
}
}
}
if(f[n] <= b){
cout << value;
return;
}
}
}
int main(){
if(fopen("1.inp", "r")){
freopen("1.inp", "r", stdin);
}
cin >> n >> a >> b;
for(int i = 1; i <= n; ++i){
cin >> arr[i];
sum[i] = arr[i] + sum[i - 1];
}
if(n <= 20) small();
else{
Medium();
}
return 0;
}
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... |