Contest Duration: ~ (local time) (90 minutes) Back to Home

Submission #315254

Source Code Expand

Copy
```#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define ALL(v) (v).begin(), (v).end()
#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))
#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)
#define SQ(x) ((x)*(x))
#define Mod(x, mod) (((x)+(mod)%(mod))
#define MP make_pair
#define PB push_back
#define Fi first
#define Se second
#define INF (1<<29)
#define EPS 1e-10
#define MOD 1000000007

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

int N,M;
ll t[5050];
int G[5005];

ll sumNum(vector<int>s){
ll res = 0;
//  rep(i,N) cout << s[i] << " "; cout << endl;
rep(i,N) res += s[i];
return res;
}

ll dfs(int n, vector<int>s){
if(M==n) return sumNum(s);
//  rep(i,N) cout << s[i] << " "; cout << endl;
//  cout << n << endl;
ll res = 0;
res = max(res, dfs(n+1, s));
//  if(n==0 || n==2 || n==3 || n==5) return res;
vector<int>ns;
for(int i=0;i<N;i++){
//    if(n==1&&i!=3) continue;
//    if(n==4&&i!=5) continue;
//    if(n==6&&i!=1) continue;
//    if(n==7&&i!=0) continue;
ns = s;
int cur = i;
int tmp = ns[cur]; ns[cur] = t[n];
//    cout << n << " " << cur << endl;
while(G[cur]>=0){
//      if(n==6 && cur == 1) cout << "ok\n";
cur = G[cur];
swap(tmp, ns[cur]);
}
res = max(res, dfs(n+1, ns));
}
return res;
}

int main(){
cin >> N;
vector<int>s(N);
rep(i,N) cin >> s[i];

G[0] = -1;
rep(i,N-1){
int a,b;
cin >> a >> b; a--; b--;
G[b] = a;
}
//  rep(i,N) cout << G[i] << " "; cout << endl;
cin >> M;
rep(i,M) cin >> t[i];

cout << dfs(0, s) << endl;
return 0;
}
```

#### Submission Info

Submission Time 2015-01-06 16:30:51+0900 D - 高橋君と木のおもちゃ raven38 C++ (G++ 4.6.4) 0 2073 Byte TLE 2053 ms 99696 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Case Name Status Exec Time Memory