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
AC × 57
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