Submission #122647


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


		double rate = 0;
		ArrayList<Double> now = new ArrayList<Double>();
		ArrayList<Integer> frag = new ArrayList<Integer>();
		ArrayList<Integer> count = new ArrayList<Integer>();
		now.add(0.0);
		frag.add(0);
		count.add(0);
		double ans = 0;

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

			if(nowcount < k){
				//System.out.printf("%3s%n", Integer.toBinaryString(nowfrag));
				for(int i = 0; i < n; i++){
					int memo = nowfrag >> i;
					int a = memo % 2;
					if(a == 0){
						double nextrate = (nowrate + rates[i]) / 2;
						now.add(nextrate);
						int nextfrag = nowfrag + (1 << i);
						frag.add(nextfrag);
						count.add(nowcount + 1);
						if(ans < nextrate){
							ans = nextrate;
						}
					}
				}
			}
		}
		System.out.printf("%-8f", 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 1364 Byte
Status TLE
Exec Time 2132 ms
Memory 55696 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 8
TLE × 26
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 505 ms 23348 KB
00_sample_02.txt AC 487 ms 23476 KB
00_sample_03.txt AC 1329 ms 27840 KB
00_sample_04.txt TLE 2039 ms 36148 KB
test_01.txt AC 490 ms 23352 KB
test_02.txt TLE 2042 ms 55288 KB
test_03.txt TLE 2043 ms 55300 KB
test_04.txt AC 492 ms 23988 KB
test_05.txt TLE 2041 ms 55416 KB
test_06.txt TLE 2044 ms 55304 KB
test_07.txt AC 516 ms 23732 KB
test_08.txt TLE 2112 ms 55268 KB
test_09.txt TLE 2043 ms 55688 KB
test_10.txt AC 505 ms 23852 KB
test_11.txt TLE 2042 ms 48008 KB
test_12.txt TLE 2132 ms 55216 KB
test_13.txt TLE 2042 ms 55312 KB
test_14.txt TLE 2092 ms 55308 KB
test_15.txt TLE 2042 ms 47880 KB
test_16.txt TLE 2039 ms 42244 KB
test_17.txt TLE 2062 ms 55316 KB
test_18.txt TLE 2043 ms 55212 KB
test_19.txt TLE 2055 ms 55312 KB
test_20.txt TLE 2060 ms 47884 KB
test_21.txt AC 611 ms 24808 KB
test_22.txt TLE 2046 ms 55300 KB
test_23.txt TLE 2038 ms 36228 KB
test_24.txt TLE 2040 ms 42372 KB
test_25.txt TLE 2043 ms 55324 KB
test_26.txt TLE 2042 ms 55696 KB
test_27.txt TLE 2042 ms 42080 KB
test_28.txt TLE 2041 ms 36420 KB
test_29.txt TLE 2042 ms 55304 KB
test_30.txt TLE 2040 ms 47752 KB