| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 307412 | KWang31 | Packing Biscuits (IOI20_biscuits) | Java | 0 ms | 0 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.
import java.io.*; import java.util.*;
public class biscuits {
static HashMap<Long, Long> dp;
public static long count_tastiness(long x, long[] a){
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 <=60; i++) {
psa[i]=psa[i-1]+((long)1<<i)*a[i];
comp((long)1<<i,psa,x);
}
grader(dp.get((long)1<<60));
return 0;
}
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);
}
}
}