Submission #2007567


Source Code Expand

Copy
#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_N = 20;
const int INF = 1e9;

int N, x[MAX_N], a[MAX_N], children[MAX_N], dp[1<<MAX_N], size[1<<MAX_N];

int main() {
  cin >> N;
  for (int i=0; i<N; i++) cin >> x[i];
  for (int i=1; i<N; i++) {
    cin >> a[i]; a[i]--;
    children[a[i]] |= (1 << i);
  }
  for (int i = 0; i < 1<<N; ++i) {
    dp[i] = INF;
    for (int j = 1; j < N; ++j) {
      if ((i>>j & 1) && !(i>>a[j] & 1)) {
        size[i] += x[j];
      }
    }
  }
  dp[0] = size[0] = 0;

  for (int i=0; i<(1<<N); i++) {
    for (int j=0; j<N; j++) {
      if (i & (1<<j)) continue;
      if ((i&children[j]) != children[j]) continue;
      int fam = i | (1<<j);
      dp[fam] = min(dp[fam], max(dp[i], size[i] + x[j]));
    }
  }

  cout << dp[(1<<N)-1] << endl;
  return 0;
}

Submission Info

Submission Time
Task D - ディスクの節約
User mon10
Language C++14 (GCC 5.4.1)
Score 600
Code Size 858 Byte
Status
Exec Time 156 ms
Memory 8448 KB

Test Cases

Set Name Score / Max Score Test Cases
All 600 / 600 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 2 ms 2304 KB
00_sample02 2 ms 2304 KB
00_sample03 2 ms 2304 KB
01_handmade00 2 ms 2304 KB
01_handmade01 2 ms 2304 KB
02_tayama_killer00 2 ms 2304 KB
10_complete00 154 ms 8448 KB
10_complete01 2 ms 2304 KB
10_complete02 2 ms 2304 KB
10_complete03 2 ms 2304 KB
20_urchin-small00 2 ms 2304 KB
20_urchin-small01 2 ms 2304 KB
20_urchin-small02 2 ms 2304 KB
20_urchin-small03 2 ms 2304 KB
20_urchin-small04 2 ms 2304 KB
21_urchin-large00 132 ms 8448 KB
21_urchin-large01 132 ms 8448 KB
21_urchin-large02 132 ms 8448 KB
21_urchin-large03 132 ms 8448 KB
21_urchin-large04 133 ms 8448 KB
30_random-small00 2 ms 2304 KB
30_random-small01 2 ms 2304 KB
30_random-small02 2 ms 2304 KB
30_random-small03 2 ms 2304 KB
30_random-small04 2 ms 2304 KB
30_random-small05 2 ms 2304 KB
30_random-small06 2 ms 2304 KB
30_random-small07 2 ms 2304 KB
30_random-small08 2 ms 2304 KB
30_random-small09 2 ms 2304 KB
30_random-small10 2 ms 2304 KB
30_random-small11 2 ms 2304 KB
30_random-small12 2 ms 2304 KB
30_random-small13 2 ms 2304 KB
30_random-small14 2 ms 2304 KB
30_random-small15 2 ms 2304 KB
30_random-small16 2 ms 2304 KB
30_random-small17 2 ms 2304 KB
30_random-small18 2 ms 2304 KB
30_random-small19 2 ms 2304 KB
30_random-small20 2 ms 2304 KB
30_random-small21 2 ms 2304 KB
30_random-small22 2 ms 2304 KB
30_random-small23 2 ms 2304 KB
30_random-small24 2 ms 2304 KB
30_random-small25 2 ms 2304 KB
30_random-small26 2 ms 2304 KB
30_random-small27 2 ms 2304 KB
30_random-small28 2 ms 2304 KB
30_random-small29 2 ms 2304 KB
31_random-large00 155 ms 8448 KB
31_random-large01 151 ms 8448 KB
31_random-large02 156 ms 8448 KB
31_random-large03 153 ms 8448 KB
31_random-large04 156 ms 8448 KB
40_boundary00 2 ms 2304 KB
40_boundary01 133 ms 8448 KB