Submission #307571

#	Time	Username	Problem	Language	Result	Execution time	Memory
307571		KWang31	Packing Biscuits (IOI20_biscuits)	Java	100 / 100	863 ms	66080 KiB

biscuits

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)a[i]<<i);
        }
        for (int i = k; i < 61; i++) {
            psa[i]=psa[i-1];
        }
        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);
        }
        
    }
}

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