Submission #2115946
Source Code Expand
#include <iostream> #include <vector> #include <algorithm> using namespace std; int n, a[22], p[22], res[1 << 22], dp[1 << 22]; vector<int>x[22]; int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 1; i < n; i++) { cin >> p[i]; p[i]--; x[p[i]].push_back(i); } for (int i = 0; i < (1 << n); i++) { bool used[22], flag = false; for (int j = 0; j < n; j++) { if ((i / (1 << j)) % 2 == 1)used[j] = true; else used[j] = false; } for (int j = 0; j < n; j++) { for (int k = 0; k < x[j].size(); k++) { if (used[j] == true && used[x[j][k]] == false) flag = true; if (used[j] == false && used[x[j][k]] == true) res[i] += a[x[j][k]]; } } if (flag == true) res[i] = (1 << 30); } for (int i = 0; i < (1 << n); i++) dp[i] = (1 << 30); dp[0] = 0; for (int i = 0; i < (1 << n); i++) { bool used[22]; for (int j = 0; j < n; j++) { if ((i / (1 << j)) % 2 == 1)used[j] = true; else used[j] = false; } for (int j = 0; j < n; j++) { if (used[j] == true) continue; dp[i + (1 << j)] = min(dp[i + (1 << j)], max(dp[i], max(res[i + (1 << j)], res[i] + a[j]))); } } cout << dp[(1 << n) - 1] << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - ディスクの節約 |
User | E869120 |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 1193 Byte |
Status | AC |
Exec Time | 347 ms |
Memory | 12544 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 600 / 600 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00_sample01, 00_sample02, 00_sample03, 01_handmade00, 01_handmade01, 02_tayama_killer00, 10_complete00, 10_complete01, 10_complete02, 10_complete03, 20_urchin-small00, 20_urchin-small01, 20_urchin-small02, 20_urchin-small03, 20_urchin-small04, 21_urchin-large00, 21_urchin-large01, 21_urchin-large02, 21_urchin-large03, 21_urchin-large04, 30_random-small00, 30_random-small01, 30_random-small02, 30_random-small03, 30_random-small04, 30_random-small05, 30_random-small06, 30_random-small07, 30_random-small08, 30_random-small09, 30_random-small10, 30_random-small11, 30_random-small12, 30_random-small13, 30_random-small14, 30_random-small15, 30_random-small16, 30_random-small17, 30_random-small18, 30_random-small19, 30_random-small20, 30_random-small21, 30_random-small22, 30_random-small23, 30_random-small24, 30_random-small25, 30_random-small26, 30_random-small27, 30_random-small28, 30_random-small29, 31_random-large00, 31_random-large01, 31_random-large02, 31_random-large03, 31_random-large04, 40_boundary00, 40_boundary01 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample01 | AC | 2 ms | 2304 KB |
00_sample02 | AC | 2 ms | 2304 KB |
00_sample03 | AC | 2 ms | 2304 KB |
01_handmade00 | AC | 2 ms | 2304 KB |
01_handmade01 | AC | 2 ms | 2304 KB |
02_tayama_killer00 | AC | 2 ms | 2304 KB |
10_complete00 | AC | 347 ms | 12544 KB |
10_complete01 | AC | 2 ms | 2304 KB |
10_complete02 | AC | 2 ms | 2304 KB |
10_complete03 | AC | 2 ms | 2304 KB |
20_urchin-small00 | AC | 2 ms | 2304 KB |
20_urchin-small01 | AC | 2 ms | 2304 KB |
20_urchin-small02 | AC | 2 ms | 2304 KB |
20_urchin-small03 | AC | 2 ms | 2304 KB |
20_urchin-small04 | AC | 2 ms | 2304 KB |
21_urchin-large00 | AC | 336 ms | 12544 KB |
21_urchin-large01 | AC | 335 ms | 12544 KB |
21_urchin-large02 | AC | 336 ms | 12544 KB |
21_urchin-large03 | AC | 336 ms | 12544 KB |
21_urchin-large04 | AC | 336 ms | 12544 KB |
30_random-small00 | AC | 2 ms | 2304 KB |
30_random-small01 | AC | 2 ms | 2304 KB |
30_random-small02 | AC | 2 ms | 2304 KB |
30_random-small03 | AC | 2 ms | 2304 KB |
30_random-small04 | AC | 2 ms | 2304 KB |
30_random-small05 | AC | 2 ms | 2304 KB |
30_random-small06 | AC | 2 ms | 2304 KB |
30_random-small07 | AC | 2 ms | 2304 KB |
30_random-small08 | AC | 2 ms | 2304 KB |
30_random-small09 | AC | 2 ms | 2304 KB |
30_random-small10 | AC | 2 ms | 2304 KB |
30_random-small11 | AC | 2 ms | 2304 KB |
30_random-small12 | AC | 2 ms | 2304 KB |
30_random-small13 | AC | 2 ms | 2304 KB |
30_random-small14 | AC | 2 ms | 2304 KB |
30_random-small15 | AC | 2 ms | 2304 KB |
30_random-small16 | AC | 2 ms | 2304 KB |
30_random-small17 | AC | 2 ms | 2304 KB |
30_random-small18 | AC | 2 ms | 2304 KB |
30_random-small19 | AC | 2 ms | 2304 KB |
30_random-small20 | AC | 2 ms | 2304 KB |
30_random-small21 | AC | 2 ms | 2304 KB |
30_random-small22 | AC | 2 ms | 2304 KB |
30_random-small23 | AC | 2 ms | 2304 KB |
30_random-small24 | AC | 2 ms | 2304 KB |
30_random-small25 | AC | 2 ms | 2304 KB |
30_random-small26 | AC | 2 ms | 2304 KB |
30_random-small27 | AC | 2 ms | 2304 KB |
30_random-small28 | AC | 2 ms | 2304 KB |
30_random-small29 | AC | 2 ms | 2304 KB |
31_random-large00 | AC | 340 ms | 12544 KB |
31_random-large01 | AC | 323 ms | 12544 KB |
31_random-large02 | AC | 321 ms | 12544 KB |
31_random-large03 | AC | 322 ms | 12544 KB |
31_random-large04 | AC | 322 ms | 12544 KB |
40_boundary00 | AC | 2 ms | 256 KB |
40_boundary01 | AC | 335 ms | 12544 KB |