Submission #307411

#	Time	Username	Problem	Language	Result	Execution time	Memory
307411		KWang31	Packing Biscuits (IOI20_biscuits)	Java	0 / 100	91 ms	10460 KiB

biscuits

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);
        }
        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);
        }
        
    }
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 21
• Subtask 4: 0 / 35
• Subtask 5: 0 / 23