Submission #307561

#TimeUsernameProblemLanguageResultExecution timeMemory
307561KWang31Packing Biscuits (IOI20_biscuits)Java
0 / 100
469 ms40560 KiB
import java.io.*; import java.util.*; public 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 <=60; i++) { if(i<k){ psa[i]=psa[i-1]+((long)1<<i)*a[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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...