Submission #298952

Source Code Expand

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    static int n;
    static int m;
    static int[] experience;
    static int[] price;
    static Set<Integer>[] combination;
    static double bestScore = 0;

    static boolean[] buyArray;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        experience = new int[n];
        for (int i = 0; i < n; i++) {
            experience[i] = sc.nextInt();
        }

        price = new int[m];
        for (int i = 0; i < m; i++) {
            price[i] = sc.nextInt();
        }

        combination = new Set[n];

        for (int i = 0; i < n; i++) {
            int k = sc.nextInt();
            combination[i] = new HashSet<Integer>();
            for(int j= 0; j < k; j++){
                combination[i].add(sc.nextInt() - 1);
            }

        }

        buyArray = new boolean[m];
        backtrack(0);
        
        System.out.println(bestScore);
    }

    public static void backtrack(int num) {
        if (num == m) {
            double score = calc();
            

            
            if(score > bestScore){
                bestScore = score;

            }
            return;
        }
        buyArray[num] = false;
        backtrack(num + 1);
        buyArray[num] = true;
        backtrack(num + 1);
    }
    
    public static double calc(){
        double sumExperience = 0;
        double sumPrice = 0;
        Set<Integer> buySet = new HashSet<Integer>();
        for(int i =0; i < m; i++){
            if(buyArray[i]){
                buySet.add(i);
            }
        }
        for(int i =0; i < n; i++){
            if(buySet.containsAll(combination[i])){
                sumExperience += experience[i];
            }
        }
        
        for(int i = 0; i < m; i++){
            if(buyArray[i]){
                sumPrice += price[i];
            }
        }
        if(sumPrice == 0){
            return 0;
        }
        return sumExperience / sumPrice;
    }
}

Submission Info

Submission Time
Task D - 買い物上手
User fdash06
Language Java (OpenJDK 1.7.0)
Score 0
Code Size 2196 Byte
Status TLE
Exec Time 2051 ms
Memory 36716 KiB

Compile Error

Note: ./Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 0 / 50 0 / 50
Status
AC × 2
AC × 6
TLE × 26
AC × 12
TLE × 81
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt
Subtask1 00_sample_00.txt, 00_sample_01.txt, 10_small_00.txt, 10_small_01.txt, 10_small_02.txt, 10_small_03.txt, 10_small_04.txt, 10_small_05.txt, 10_small_06.txt, 10_small_07.txt, 10_small_08.txt, 10_small_09.txt, 10_small_10.txt, 10_small_11.txt, 10_small_12.txt, 10_small_13.txt, 10_small_14.txt, 10_small_15.txt, 10_small_16.txt, 10_small_17.txt, 10_small_18.txt, 10_small_19.txt, 10_small_20.txt, 10_small_21.txt, 10_small_22.txt, 10_small_23.txt, 10_small_24.txt, 10_small_25.txt, 10_small_26.txt, 10_small_27.txt, 10_small_28.txt, 10_small_29.txt
Subtask2 00_sample_00.txt, 00_sample_01.txt, 10_small_00.txt, 10_small_01.txt, 10_small_02.txt, 10_small_03.txt, 10_small_04.txt, 10_small_05.txt, 10_small_06.txt, 10_small_07.txt, 10_small_08.txt, 10_small_09.txt, 10_small_10.txt, 10_small_11.txt, 10_small_12.txt, 10_small_13.txt, 10_small_14.txt, 10_small_15.txt, 10_small_16.txt, 10_small_17.txt, 10_small_18.txt, 10_small_19.txt, 10_small_20.txt, 10_small_21.txt, 10_small_22.txt, 10_small_23.txt, 10_small_24.txt, 10_small_25.txt, 10_small_26.txt, 10_small_27.txt, 10_small_28.txt, 10_small_29.txt, 20_rand_00.txt, 20_rand_01.txt, 20_rand_02.txt, 20_rand_03.txt, 20_rand_04.txt, 20_rand_05.txt, 20_rand_06.txt, 20_rand_07.txt, 20_rand_08.txt, 20_rand_09.txt, 20_rand_10.txt, 20_rand_11.txt, 20_rand_12.txt, 20_rand_13.txt, 20_rand_14.txt, 20_rand_15.txt, 20_rand_16.txt, 20_rand_17.txt, 20_rand_18.txt, 20_rand_19.txt, 20_rand_20.txt, 20_rand_21.txt, 20_rand_22.txt, 20_rand_23.txt, 20_rand_24.txt, 20_rand_25.txt, 20_rand_26.txt, 20_rand_27.txt, 20_rand_28.txt, 20_rand_29.txt, 30_large_0.txt, 30_large_1.txt, 30_large_2.txt, 30_large_3.txt, 30_large_4.txt, 30_large_5.txt, 30_large_6.txt, 30_large_7.txt, 30_large_8.txt, 30_large_9.txt, 40_max_0.txt, 40_max_1.txt, 40_max_2.txt, 40_max_3.txt, 40_max_4.txt, 40_max_5.txt, 40_max_6.txt, 40_max_7.txt, 40_max_8.txt, 40_max_9.txt, 50_killer_0.txt, 50_killer_1.txt, 50_killer_2.txt, 50_killer_3.txt, 50_killer_4.txt, 50_killer_5.txt, 50_killer_6.txt, 50_killer_7.txt, 50_killer_8.txt, 50_killer_9.txt, 60_corner_0.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 469 ms 23332 KiB
00_sample_01.txt AC 475 ms 23480 KiB
10_small_00.txt TLE 2039 ms 33284 KiB
10_small_01.txt TLE 2039 ms 33252 KiB
10_small_02.txt TLE 2045 ms 33124 KiB
10_small_03.txt TLE 2038 ms 33016 KiB
10_small_04.txt TLE 2041 ms 33156 KiB
10_small_05.txt TLE 2039 ms 33148 KiB
10_small_06.txt AC 469 ms 23416 KiB
10_small_07.txt TLE 2041 ms 33120 KiB
10_small_08.txt TLE 2040 ms 32884 KiB
10_small_09.txt TLE 2039 ms 33156 KiB
10_small_10.txt TLE 2038 ms 33140 KiB
10_small_11.txt TLE 2040 ms 32756 KiB
10_small_12.txt TLE 2040 ms 33160 KiB
10_small_13.txt TLE 2039 ms 32836 KiB
10_small_14.txt AC 465 ms 23460 KiB
10_small_15.txt TLE 2039 ms 32640 KiB
10_small_16.txt TLE 2045 ms 32868 KiB
10_small_17.txt TLE 2040 ms 32980 KiB
10_small_18.txt TLE 2038 ms 32744 KiB
10_small_19.txt AC 928 ms 32768 KiB
10_small_20.txt TLE 2040 ms 33124 KiB
10_small_21.txt TLE 2041 ms 32864 KiB
10_small_22.txt TLE 2051 ms 32996 KiB
10_small_23.txt TLE 2042 ms 32608 KiB
10_small_24.txt TLE 2040 ms 33212 KiB
10_small_25.txt TLE 2039 ms 32956 KiB
10_small_26.txt AC 484 ms 23412 KiB
10_small_27.txt TLE 2041 ms 32992 KiB
10_small_28.txt TLE 2039 ms 33032 KiB
10_small_29.txt TLE 2039 ms 32608 KiB
20_rand_00.txt TLE 2048 ms 33168 KiB
20_rand_01.txt TLE 2040 ms 34452 KiB
20_rand_02.txt TLE 2041 ms 32900 KiB
20_rand_03.txt TLE 2049 ms 34672 KiB
20_rand_04.txt AC 480 ms 23464 KiB
20_rand_05.txt TLE 2040 ms 33840 KiB
20_rand_06.txt AC 1364 ms 34120 KiB
20_rand_07.txt TLE 2041 ms 33012 KiB
20_rand_08.txt TLE 2038 ms 34788 KiB
20_rand_09.txt TLE 2039 ms 33000 KiB
20_rand_10.txt TLE 2039 ms 34876 KiB
20_rand_11.txt TLE 2040 ms 34956 KiB
20_rand_12.txt TLE 2038 ms 34380 KiB
20_rand_13.txt AC 887 ms 34524 KiB
20_rand_14.txt TLE 2040 ms 32920 KiB
20_rand_15.txt TLE 2041 ms 32948 KiB
20_rand_16.txt AC 478 ms 24048 KiB
20_rand_17.txt TLE 2039 ms 34840 KiB
20_rand_18.txt TLE 2039 ms 32864 KiB
20_rand_19.txt TLE 2040 ms 34020 KiB
20_rand_20.txt AC 687 ms 33732 KiB
20_rand_21.txt TLE 2039 ms 32944 KiB
20_rand_22.txt TLE 2040 ms 32740 KiB
20_rand_23.txt TLE 2039 ms 33360 KiB
20_rand_24.txt TLE 2042 ms 34780 KiB
20_rand_25.txt TLE 2039 ms 33200 KiB
20_rand_26.txt TLE 2039 ms 36716 KiB
20_rand_27.txt TLE 2039 ms 32992 KiB
20_rand_28.txt TLE 2040 ms 32888 KiB
20_rand_29.txt TLE 2040 ms 32548 KiB
30_large_0.txt TLE 2038 ms 33896 KiB
30_large_1.txt TLE 2038 ms 32904 KiB
30_large_2.txt TLE 2038 ms 33268 KiB
30_large_3.txt TLE 2039 ms 34020 KiB
30_large_4.txt TLE 2040 ms 35280 KiB
30_large_5.txt TLE 2040 ms 35152 KiB
30_large_6.txt TLE 2038 ms 34032 KiB
30_large_7.txt TLE 2040 ms 34780 KiB
30_large_8.txt TLE 2042 ms 33320 KiB
30_large_9.txt TLE 2040 ms 33132 KiB
40_max_0.txt TLE 2048 ms 33848 KiB
40_max_1.txt TLE 2039 ms 34132 KiB
40_max_2.txt TLE 2040 ms 33564 KiB
40_max_3.txt TLE 2040 ms 33384 KiB
40_max_4.txt TLE 2041 ms 33064 KiB
40_max_5.txt TLE 2039 ms 33576 KiB
40_max_6.txt TLE 2039 ms 33264 KiB
40_max_7.txt TLE 2042 ms 33272 KiB
40_max_8.txt TLE 2039 ms 33660 KiB
40_max_9.txt TLE 2039 ms 33268 KiB
50_killer_0.txt TLE 2039 ms 34880 KiB
50_killer_1.txt TLE 2044 ms 34564 KiB
50_killer_2.txt TLE 2039 ms 34804 KiB
50_killer_3.txt TLE 2039 ms 34540 KiB
50_killer_4.txt TLE 2039 ms 33716 KiB
50_killer_5.txt TLE 2045 ms 33896 KiB
50_killer_6.txt TLE 2044 ms 34452 KiB
50_killer_7.txt TLE 2040 ms 34800 KiB
50_killer_8.txt TLE 2040 ms 34376 KiB
50_killer_9.txt TLE 2041 ms 35008 KiB
60_corner_0.txt AC 491 ms 24068 KiB