Submission #307208
Source Code Expand
#include <iostream> #include <sstream> #include <fstream> #include <string> #include <vector> #include <deque> #include <queue> #include <stack> #include <set> #include <map> #include <algorithm> #include <utility> #include <bitset> #include <cmath> #include <cstdlib> #include <ctime> #include <cstring> #include <cstdio> using namespace std; #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++) #define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) int N, M; int S[102], T[102], K[102]; int A[102][102]; double solve() { double ans = 0; for (int Set = 0; Set < (1<<N); Set++) { bitset<102> bs; int exp = 0; for (int i = 0; i < N; i++) { if (!(Set >> i & 1)) continue; exp += S[i]; for (int j = 0; j < K[i]; j++) { bs.set(A[i][j]); } } int sum = 0; for (int i = 0; i < M; i++) { if (bs[i]) sum += T[i]; } ans = max(ans, (double)exp / sum); } return ans; } int main() { while (cin >> N >> M) { for(size_t i = 0; i < N; i++) { cin>>S[i]; } for(size_t i = 0; i < M; i++) { cin>>T[i]; } for(size_t i = 0; i < N; i++) { cin>>K[i]; for(size_t j = 0; j < K[i]; j++) { cin>>A[i][j]; A[i][j]--; } } printf("%lf\n", solve()); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - 買い物上手 |
User | brly |
Language | C++ (G++ 4.6.4) |
Score | 50 |
Code Size | 1417 Byte |
Status | WA |
Exec Time | 2032 ms |
Memory | 940 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 50 / 50 | 0 / 50 | ||||||||||
Status |
|
|
|
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 | 23 ms | 804 KB |
00_sample_01.txt | AC | 23 ms | 920 KB |
10_small_00.txt | AC | 24 ms | 796 KB |
10_small_01.txt | AC | 24 ms | 800 KB |
10_small_02.txt | AC | 22 ms | 928 KB |
10_small_03.txt | AC | 22 ms | 916 KB |
10_small_04.txt | AC | 23 ms | 916 KB |
10_small_05.txt | AC | 23 ms | 792 KB |
10_small_06.txt | AC | 24 ms | 796 KB |
10_small_07.txt | AC | 22 ms | 788 KB |
10_small_08.txt | AC | 24 ms | 800 KB |
10_small_09.txt | AC | 23 ms | 804 KB |
10_small_10.txt | AC | 24 ms | 800 KB |
10_small_11.txt | AC | 23 ms | 800 KB |
10_small_12.txt | AC | 22 ms | 800 KB |
10_small_13.txt | AC | 23 ms | 924 KB |
10_small_14.txt | AC | 24 ms | 796 KB |
10_small_15.txt | AC | 24 ms | 796 KB |
10_small_16.txt | AC | 24 ms | 924 KB |
10_small_17.txt | AC | 24 ms | 804 KB |
10_small_18.txt | AC | 24 ms | 904 KB |
10_small_19.txt | AC | 23 ms | 792 KB |
10_small_20.txt | AC | 24 ms | 732 KB |
10_small_21.txt | AC | 24 ms | 744 KB |
10_small_22.txt | AC | 23 ms | 924 KB |
10_small_23.txt | AC | 23 ms | 924 KB |
10_small_24.txt | AC | 21 ms | 796 KB |
10_small_25.txt | AC | 24 ms | 796 KB |
10_small_26.txt | AC | 23 ms | 804 KB |
10_small_27.txt | AC | 22 ms | 792 KB |
10_small_28.txt | AC | 23 ms | 924 KB |
10_small_29.txt | AC | 22 ms | 784 KB |
20_rand_00.txt | AC | 32 ms | 812 KB |
20_rand_01.txt | TLE | 2032 ms | 924 KB |
20_rand_02.txt | AC | 25 ms | 928 KB |
20_rand_03.txt | WA | 22 ms | 804 KB |
20_rand_04.txt | AC | 23 ms | 676 KB |
20_rand_05.txt | WA | 354 ms | 764 KB |
20_rand_06.txt | TLE | 2031 ms | 888 KB |
20_rand_07.txt | AC | 27 ms | 800 KB |
20_rand_08.txt | TLE | 2031 ms | 920 KB |
20_rand_09.txt | AC | 23 ms | 788 KB |
20_rand_10.txt | WA | 24 ms | 788 KB |
20_rand_11.txt | TLE | 2032 ms | 872 KB |
20_rand_12.txt | TLE | 2031 ms | 932 KB |
20_rand_13.txt | WA | 24 ms | 796 KB |
20_rand_14.txt | TLE | 2031 ms | 860 KB |
20_rand_15.txt | AC | 22 ms | 800 KB |
20_rand_16.txt | WA | 107 ms | 932 KB |
20_rand_17.txt | WA | 134 ms | 728 KB |
20_rand_18.txt | AC | 36 ms | 812 KB |
20_rand_19.txt | WA | 24 ms | 928 KB |
20_rand_20.txt | WA | 22 ms | 804 KB |
20_rand_21.txt | AC | 25 ms | 924 KB |
20_rand_22.txt | AC | 22 ms | 800 KB |
20_rand_23.txt | WA | 25 ms | 928 KB |
20_rand_24.txt | WA | 32 ms | 932 KB |
20_rand_25.txt | WA | 24 ms | 928 KB |
20_rand_26.txt | WA | 25 ms | 800 KB |
20_rand_27.txt | WA | 141 ms | 804 KB |
20_rand_28.txt | TLE | 2030 ms | 804 KB |
20_rand_29.txt | WA | 22 ms | 928 KB |
30_large_0.txt | WA | 23 ms | 928 KB |
30_large_1.txt | WA | 23 ms | 804 KB |
30_large_2.txt | WA | 23 ms | 800 KB |
30_large_3.txt | WA | 22 ms | 756 KB |
30_large_4.txt | WA | 23 ms | 928 KB |
30_large_5.txt | WA | 22 ms | 920 KB |
30_large_6.txt | WA | 22 ms | 808 KB |
30_large_7.txt | WA | 24 ms | 912 KB |
30_large_8.txt | WA | 23 ms | 924 KB |
30_large_9.txt | WA | 23 ms | 732 KB |
40_max_0.txt | WA | 22 ms | 928 KB |
40_max_1.txt | WA | 23 ms | 932 KB |
40_max_2.txt | WA | 23 ms | 800 KB |
40_max_3.txt | WA | 24 ms | 808 KB |
40_max_4.txt | WA | 25 ms | 748 KB |
40_max_5.txt | WA | 24 ms | 792 KB |
40_max_6.txt | WA | 23 ms | 920 KB |
40_max_7.txt | WA | 23 ms | 804 KB |
40_max_8.txt | WA | 22 ms | 804 KB |
40_max_9.txt | WA | 25 ms | 928 KB |
50_killer_0.txt | TLE | 2032 ms | 924 KB |
50_killer_1.txt | WA | 24 ms | 928 KB |
50_killer_2.txt | WA | 24 ms | 800 KB |
50_killer_3.txt | TLE | 2031 ms | 940 KB |
50_killer_4.txt | TLE | 2030 ms | 940 KB |
50_killer_5.txt | WA | 22 ms | 804 KB |
50_killer_6.txt | WA | 23 ms | 732 KB |
50_killer_7.txt | WA | 22 ms | 800 KB |
50_killer_8.txt | TLE | 2032 ms | 932 KB |
50_killer_9.txt | TLE | 2030 ms | 928 KB |
60_corner_0.txt | WA | 24 ms | 732 KB |