Submission #123063


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>();
		now.add(0.0);
		frag.add(0);
		

		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++){
				int memo = nowfrag >> i;
			   	int a = memo % 2;
			if(a == 0 && nowrate < rates[i]){
				double nextrate = (nowrate + rates[i]) / 2;
				now.add(nextrate);
				int nextfrag = nowfrag + (1 << i);
				frag.add(nextfrag);
				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
Task C - AtCoderプログラミング講座
User wapiko
Language Java (OpenJDK 1.7.0)
Score 0
Code Size 1959 Byte
Status TLE
Exec Time 2061 ms
Memory 57732 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 450 ms 23388 KB
00_sample_02.txt AC 440 ms 23516 KB
00_sample_03.txt AC 436 ms 23640 KB
00_sample_04.txt AC 456 ms 23512 KB
test_01.txt AC 448 ms 23500 KB
test_02.txt TLE 2047 ms 57732 KB
test_03.txt TLE 2039 ms 43132 KB
test_04.txt AC 441 ms 23868 KB
test_05.txt TLE 2041 ms 50560 KB
test_06.txt TLE 2037 ms 43008 KB
test_07.txt AC 450 ms 23768 KB
test_08.txt TLE 2059 ms 57696 KB
test_09.txt TLE 2038 ms 43128 KB
test_10.txt AC 455 ms 23904 KB
test_11.txt TLE 2038 ms 36868 KB
test_12.txt TLE 2042 ms 36624 KB
test_13.txt TLE 2040 ms 42908 KB
test_14.txt AC 1884 ms 28272 KB
test_15.txt TLE 2038 ms 36856 KB
test_16.txt TLE 2040 ms 36600 KB
test_17.txt TLE 2061 ms 42880 KB
test_18.txt TLE 2039 ms 43140 KB
test_19.txt TLE 2040 ms 36864 KB
test_20.txt TLE 2040 ms 36828 KB
test_21.txt AC 452 ms 24036 KB
test_22.txt TLE 2039 ms 36492 KB
test_23.txt TLE 2040 ms 36348 KB
test_24.txt TLE 2043 ms 36368 KB
test_25.txt TLE 2042 ms 42872 KB
test_26.txt TLE 2038 ms 36624 KB
test_27.txt TLE 2041 ms 36552 KB
test_28.txt AC 441 ms 23528 KB
test_29.txt TLE 2040 ms 42892 KB
test_30.txt TLE 2039 ms 30584 KB