Submission #2489923

---

Source Code Expand

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long lli;
typedef double lld;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<double> vdl;
typedef vector<vector<lli>> mat;
typedef vector<vdl> mad;
typedef unordered_map<lli,vector<lli>> graph;
typedef complex<double> cmp;
typedef vector<cmp> vcl;
 
lli n;
unordered_map<lli,lli> x;
graph t;
vll dp,dq;
 
bool check(lli b,lli c){
  if(b&c) return false;
  for(lli d : t[c]){
    if((b&d) == 0) return false;
  }
  return true;
}
 
int main(){
  cin >> n;
  lli ub = 1ll << n;
  for(lli i = 1ll;i < ub;i <<= 1) cin >> x[i];
  for(lli i = 2ll;i < ub;i <<= 1){
    lli a;
    cin >> a;
    t[1ll << (a-1)].push_back(i);
  }
  dp = vll(ub,INT_MAX);
  dq = vll(ub,INT_MAX);
  dp[0] = 0;
  dq[0] = 0;
  for(lli b = 0;b < ub;b++){
    for(lli c = 1ll;c < ub;c <<= 1){
      if(check(b,c)){
        lli y = dp[b]+x[c];
        dq[b|c] = min(dq[b|c],max(dq[b],y));
        for(lli z : t[c]) y -= x[z];
        dp[b|c] = min(dp[b|c],y);
      }
    }
  }
  cout << dq[ub-1] << endl;
  return 0;
}

Submission Info

Judge Result