| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 307412 | KWang31 | 비스킷 담기 (IOI20_biscuits) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
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);
}
}
}