提出 #3818115

ソースコード 拡げる

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

int n;
int dp[2000000] = {0};
int memo[25] = {0};
vector<int> edge[25];

int solve(int x);
int calc(int x);

int main() {
  cin >> n;
  for(int i = 0; i < n; ++i) cin >> memo[i];
  for(int i = 1; i < n; ++i) {
    int x;
    cin >> x;
    --x;
    edge[x].push_back(i);
  }
  for(int i = 0; i < (1 << n); ++i) dp[i] = -1;
  for(int i = 0; i < n; ++i)
    if(edge[i].size() == 0) dp[(1 << i)] = memo[i];
  cout << solve(1) << endl;
  return 0;
}

int solve(int x) {
  if(dp[x] != -1) return dp[x];
  int ans = 0, now = 0;
  now = calc(x);
  ans = 2000000000;
  for(int i = 0; i < n; ++i)
    if((x & (1 << i)) == (1 << i)) {
      int nextx = 0;
      for(int j = 0; j < edge[i].size(); ++j)
        nextx += 1 << edge[i][j];
      ans = min(ans, max(now + calc(nextx),
                         solve(nextx + x - (1 << i))));
    }
  return dp[x] = ans;
}

int calc(int x) {
  int ans = 0;
  for(int i = 0; i < n; ++i)
    if((x & (1 << i)) == (1 << i)) ans += memo[i];
  return ans;
}

提出情報

提出日時
問題 D - ディスクの節約
ユーザ m_tsubasa
言語 C++14 (GCC 5.4.1)
得点 600
コード長 1116 Byte
結果 AC
実行時間 177 ms
メモリ 6400 KiB

ジャッジ結果

セット名 All
得点 / 配点 600 / 600
結果
AC × 57
セット名 テストケース
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
ケース名 結果 実行時間 メモリ
00_sample01 AC 1 ms 256 KiB
00_sample02 AC 1 ms 256 KiB
00_sample03 AC 1 ms 256 KiB
01_handmade00 AC 1 ms 256 KiB
01_handmade01 AC 1 ms 256 KiB
02_tayama_killer00 AC 1 ms 256 KiB
10_complete00 AC 4 ms 6400 KiB
10_complete01 AC 1 ms 256 KiB
10_complete02 AC 1 ms 256 KiB
10_complete03 AC 1 ms 256 KiB
20_urchin-small00 AC 1 ms 256 KiB
20_urchin-small01 AC 1 ms 256 KiB
20_urchin-small02 AC 1 ms 256 KiB
20_urchin-small03 AC 1 ms 256 KiB
20_urchin-small04 AC 1 ms 256 KiB
21_urchin-large00 AC 174 ms 6400 KiB
21_urchin-large01 AC 174 ms 6400 KiB
21_urchin-large02 AC 177 ms 6400 KiB
21_urchin-large03 AC 174 ms 6400 KiB
21_urchin-large04 AC 176 ms 6400 KiB
30_random-small00 AC 1 ms 256 KiB
30_random-small01 AC 1 ms 256 KiB
30_random-small02 AC 1 ms 256 KiB
30_random-small03 AC 1 ms 256 KiB
30_random-small04 AC 1 ms 256 KiB
30_random-small05 AC 1 ms 256 KiB
30_random-small06 AC 1 ms 256 KiB
30_random-small07 AC 1 ms 256 KiB
30_random-small08 AC 1 ms 256 KiB
30_random-small09 AC 1 ms 256 KiB
30_random-small10 AC 1 ms 256 KiB
30_random-small11 AC 1 ms 256 KiB
30_random-small12 AC 1 ms 256 KiB
30_random-small13 AC 1 ms 256 KiB
30_random-small14 AC 1 ms 256 KiB
30_random-small15 AC 1 ms 256 KiB
30_random-small16 AC 1 ms 256 KiB
30_random-small17 AC 1 ms 256 KiB
30_random-small18 AC 1 ms 256 KiB
30_random-small19 AC 1 ms 256 KiB
30_random-small20 AC 1 ms 256 KiB
30_random-small21 AC 1 ms 256 KiB
30_random-small22 AC 1 ms 256 KiB
30_random-small23 AC 1 ms 256 KiB
30_random-small24 AC 1 ms 256 KiB
30_random-small25 AC 1 ms 256 KiB
30_random-small26 AC 1 ms 256 KiB
30_random-small27 AC 1 ms 256 KiB
30_random-small28 AC 1 ms 256 KiB
30_random-small29 AC 1 ms 256 KiB
31_random-large00 AC 4 ms 6400 KiB
31_random-large01 AC 6 ms 6400 KiB
31_random-large02 AC 6 ms 6400 KiB
31_random-large03 AC 6 ms 6400 KiB
31_random-large04 AC 4 ms 6400 KiB
40_boundary00 AC 1 ms 256 KiB
40_boundary01 AC 174 ms 6400 KiB