Contest Duration: - (local time) (120 minutes) Back to Home

Submission #123079

Source Code Expand

Copy
```import java.util.ArrayList;
import java.util.Scanner;

public class Main {

Scanner sc = new Scanner(System.in);
public void run() {
int n = sc.nextInt();
int k = sc.nextInt();
calc(n, k);

}
public void calc(int n, int k){
int[] rates = new int[n];
for(int i = 0; i < n; i++){
rates[i] = sc.nextInt();
}

rates = mergesort(rates);
double ans = 0;

ArrayList<Double> now = new ArrayList<Double>();
ArrayList<Integer> frag = new ArrayList<Integer>();

while(now.size() != 0){
double nowrate = now.get(0);
int nowfrag = frag.get(0);
now.remove(0);
frag.remove(0);

//System.out.printf("%3s%n", Integer.toBinaryString(nowfrag));
for(int i = 0; i < k; i++){
if(nowrate > rates[i]) break;
int memo = nowfrag >> i;
int a = memo % 2;
if(a == 0){
double nextrate = (nowrate + rates[i]) / 2;
int nextfrag = nowfrag + (1 << i);
if(ans < nextrate){
ans = nextrate;
}
}
}
}
System.out.printf("%-8f", ans);
}

public int[] mergesort(int[] a){
if(a.length == 1) return a;
else{
int l1 = a.length / 2;
int l2 = a.length - l1;

int[] a1 = new int[l1];
int[] a2 = new int[l2];
for(int i = 0; i < l1; i++) a1[i] = a[i];
for(int i = 0; i < l2; i++) a2[i] = a[i+l1];
a1 = mergesort(a1);
a2 = mergesort(a2);

int[] ans = merge(a1, a2);
return ans;
}
}
public int[] merge(int[] a1, int[]a2){
int i = 0;
int j = 0;
int[] ans = new int[a1.length + a2.length];
int c = 0;
while(i < a1.length || j < a2.length){
if(j >= a2.length || (i < a1.length && a1[i] > a2[j]) ){
ans[c] = a1[i];
i = i + 1;
c= c + 1;
}
else{
ans[c] = a2[j];
j = j + 1;
c = c + 1;
}
}
return ans;
}

public static void main(String[] args) {
new Main().run();
}
}
```

#### Submission Info

Submission Time 2013-12-12 22:50:21+0900 C - AtCoderプログラミング講座 wapiko Java (OpenJDK 1.7.0) 0 1976 Byte TLE 2097 ms 57736 KB

#### Judge Result

Set Name All
Score / Max Score 0 / 100
Status
 AC × 11 TLE × 23
Set Name Test Cases
All 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 445 ms 23524 KB
00_sample_02.txt AC 449 ms 23400 KB
00_sample_03.txt AC 452 ms 23512 KB
00_sample_04.txt AC 459 ms 23540 KB
test_01.txt AC 451 ms 23520 KB
test_02.txt TLE 2049 ms 57736 KB
test_03.txt TLE 2038 ms 43136 KB
test_04.txt AC 467 ms 23656 KB
test_05.txt TLE 2097 ms 57664 KB
test_06.txt TLE 2038 ms 43012 KB
test_07.txt AC 470 ms 23772 KB
test_08.txt TLE 2047 ms 57724 KB
test_09.txt TLE 2040 ms 43136 KB
test_10.txt AC 459 ms 23656 KB
test_11.txt TLE 2041 ms 36788 KB
test_12.txt TLE 2038 ms 36740 KB
test_13.txt TLE 2040 ms 43132 KB
test_14.txt AC 1910 ms 28556 KB
test_15.txt TLE 2039 ms 36872 KB
test_16.txt TLE 2038 ms 36364 KB
test_17.txt TLE 2061 ms 42896 KB
test_18.txt TLE 2060 ms 43016 KB
test_19.txt TLE 2042 ms 36868 KB
test_20.txt TLE 2038 ms 36736 KB
test_21.txt AC 474 ms 23764 KB
test_22.txt TLE 2041 ms 36748 KB
test_23.txt TLE 2040 ms 36332 KB
test_24.txt TLE 2041 ms 36360 KB
test_25.txt TLE 2040 ms 43140 KB
test_26.txt TLE 2040 ms 36868 KB
test_27.txt TLE 2038 ms 36492 KB
test_28.txt AC 444 ms 23520 KB
test_29.txt TLE 2046 ms 43156 KB
test_30.txt TLE 2037 ms 30512 KB