# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
151703 | Ruxandra985 | Bali Sculptures (APIO15_sculpture) | C++14 | 2 ms | 420 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.
/// aliens pe subtaskuri suna... mInUnAt
#include <cstdio>
#include <iostream>
#define DIMN 2010
#define INF 4000000000000
using namespace std;
int v[DIMN],cnt[DIMN],n;
long long dp[DIMN],sp[DIMN];
int check (long long lambda , long long &sol){ /// sol = dp[n] , return = cnt[n]
int i,poz,j;
long long mini;
for (i=1;i<=n;i++){
mini = (dp[i-1] | v[i]) + lambda * (cnt[i-1] + 1);
poz = i-1;
for (j=i-2;j>=0;j--){
if (mini > (dp[j] | (sp[i] - sp[j])) + lambda*(cnt[j] + 1)){
mini = (dp[j] | (sp[i] - sp[j])) + lambda*(cnt[j] + 1);
poz = j;
}
}
dp[i] = (dp[poz] | (sp[i] - sp[poz]));
cnt[i] = cnt[poz] + 1;
}
sol = dp[n] + lambda * cnt[n];
return cnt[n];
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int a,b,i,x;
long long sol , solfinal,st,dr,mid,lastok;
fscanf (fin,"%d%d%d",&n,&a,&b);
for (i=1;i<=n;i++){
fscanf (fin,"%d",&v[i]);
sp[i] = sp[i-1] + v[i];
}
if (a!=1){
solfinal =0;
for (x=a;x<=b;x++){ /// aliens pe FIX x intervale
st = -INF/2;
dr = INF/2;
while (st<=dr){
mid = (st + dr)/2;
sol = 0;
if (check(mid,sol) > x)
st = mid + 1;
else {
lastok = mid;
dr = mid - 1;
}
}
sol = 0;
check (lastok,sol);
if (x == a)
solfinal = sol - (long long)x * lastok;
else solfinal = min (solfinal , sol - (long long)x * lastok);
}
}
else { /// a = 1 , b e idk , deci poti sa selectezi CEL MULT b intervale
solfinal = 0;
st = -INF/2;
dr = INF/2;
while (st<=dr){
mid = (st + dr)/2;
sol = 0;
if (check(mid,sol) > b)
st = mid + 1;
else{
lastok = mid;
dr = mid - 1;
}
}
sol = 0;
x = check (lastok,sol);
solfinal = sol - (long long)x * lastok;
}
fprintf (fout,"%lld",solfinal);
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... |