This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import java.io.*; import java.util.*;
class biscuits {
static HashMap<Long, Long> dp;
public static long count_tastiness(long x, long[] a){
int k=a.length;
dp=new HashMap<>();
dp.put((long)0,(long)0);
dp.put((long)1,(long)1);
//psa is bounded by 10^{18}
long[] psa=new long[61];
psa[0]=a[0];
for (int i = 1; i <k; i++) {
psa[i]=psa[i-1]+((long)1<<i*a[i]);
}
for (int i = 1; i <=60; i++) {
comp((long)1<<i,psa,x);
}
return dp.get((long)1<<60);
}
public static void comp(long n, long[] psa, long x){
if(dp.get(n)==null){
int i=0;
long p=1;
while(p<n){
p*=2; i++;
}
p/=2; i--;
long ans=dp.get(p);
long min=Math.max(0,Math.min((long)n-p,(long) 1+psa[i]/x-p));
comp(min,psa,x);
ans+=dp.get(min);
dp.put(n, ans);
}
}
}
# | 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... |