Submission #856512


Source Code Expand

Copy
/**
 * Created on 2016/08/28.
 */

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int A = sc.nextInt();

        ArrayList<Integer> nums = new ArrayList<>();

        for(int i=0; i<N; i++){
            nums.add(sc.nextInt());
        }

        Collections.sort(nums);

        long ret = dfs(nums, 0, 1, 0, A);

        System.out.println(ret);

    }

    private static long dfs(ArrayList<Integer> nums, int idx, int depth, int acc, int A) {

        boolean flag = false;

        // base
        if(nums.get(idx) + acc > A * depth){
            return 0;
        }

        if(nums.get(idx) + acc == A * depth){
            flag = true;
            if(idx == nums.size() - 1){
                return 1;
            }
        }

        if(idx == nums.size() - 1){
            return 0;
        }

        // search

        long ret = 0;
        ret += dfs(nums, idx+1, depth+1, acc + nums.get(idx), A);
        ret += dfs(nums, idx+1, depth, acc, A);
        if(flag){
            ret++;
        }

        return ret;

    }


    // Algorithms
    private static ArrayList<Integer> getPrimeNumbers(int upperLimit) {
        ArrayList<Integer> ret = new ArrayList<Integer>();

        ret.add(2);
        ret.add(3);

        for (int i = 5; i <= upperLimit; i += 2) {
            boolean isPrime = true;
            // 素数で平方根まで試し割りしてみる
            for (int j = 2; j * j <= i; j++) {
                if (i % j == 0) {
                    isPrime = false;
                    break;
                }
            }

            if (isPrime) {
                ret.add(i);
            }
        }
        return ret;
    }

    // View Method
    //* List
    public static <T> void viewList(List<T> list) {
        for (T item : list) {
            System.out.print(item + "\t");
        }
        System.out.println("");
    }

    //* Map
    public static <K, V> void viewMap(Map<K, V> map) {
        Set<K> keys = map.keySet();
        for (K key : keys) {
            System.out.print("(" + key + ", " + map.get(key) + ")\t");
        }
        System.out.println("");
    }

    //* Matrix
    public static void viewIntMatrix(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                System.out.print(matrix[i][j] + "\t");
            }
            System.out.println("");
        }
    }
}

Submission Info

Submission Time
Task C - Tak and Cards
User neoki
Language Java8 (OpenJDK 1.8.0)
Score 200
Code Size 2655 Byte
Status TLE
Exec Time 2120 ms
Memory 10360 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 200 / 200 0 / 100
Status
AC × 3
TLE × 1
AC × 12
AC × 14
TLE × 10
Set Name Test Cases
Sample example_01.txt, example_02.txt, example_03.txt, example_04.txt
Subtask1 example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt
All example_01.txt, example_02.txt, example_03.txt, example_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt
Case Name Status Exec Time Memory
example_01.txt AC 212 ms 9936 KB
example_02.txt AC 200 ms 9420 KB
example_03.txt AC 196 ms 9544 KB
example_04.txt TLE 2107 ms 10056 KB
subtask1_01.txt AC 212 ms 9552 KB
subtask1_02.txt AC 224 ms 9804 KB
subtask1_03.txt AC 200 ms 9424 KB
subtask1_04.txt AC 228 ms 10068 KB
subtask1_05.txt AC 224 ms 9548 KB
subtask1_06.txt AC 196 ms 9416 KB
subtask1_07.txt AC 192 ms 9424 KB
subtask1_08.txt AC 212 ms 9680 KB
subtask1_09.txt AC 196 ms 9428 KB
subtask2_01.txt TLE 2107 ms 10192 KB
subtask2_02.txt TLE 2103 ms 10048 KB
subtask2_03.txt TLE 2109 ms 10360 KB
subtask2_04.txt TLE 2107 ms 10056 KB
subtask2_05.txt AC 196 ms 9680 KB
subtask2_06.txt TLE 2103 ms 9936 KB
subtask2_07.txt TLE 2103 ms 10064 KB
subtask2_08.txt TLE 2103 ms 10044 KB
subtask2_09.txt TLE 2120 ms 9936 KB
subtask2_10.txt AC 207 ms 9552 KB
subtask2_11.txt TLE 2103 ms 10068 KB