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

Submission #242405

Source Code Expand

Copy
```#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<25;
typedef pair<int,int> P;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vertex;
typedef vector<vertex> graph;

ll dp[5010][5010];

int main(){
int n;
cin>>n;
vector<ll> s(n);
for(int i = 0; i < n; i++){
cin>>s[i];
}
graph g(n);
for(int i = 0; i < n-1; i++){
int a,b;
cin>>a>>b;
a--;b--;
g[a].push_back(b);
}
int m;
cin>>m;
vector<ll> t(m);
for(int i = 0; i < m; i++){
cin>>t[i];
}
sort(t.begin(), t.end());
reverse(t.begin(), t.end());
ll sum = 0;
for(int i = 0; i < n; i++){
sum += s[i];
}
ll res = sum;
memset(dp, -1, sizeof(dp));
for(int i = n-1; i >= 0; i--){
dp[i][0] = 0;
dp[i][1] = s[i];
for(int j = 0; j < g[i].size(); j++){
for(int k = 0; k <= j; k++){
for(int l = 1; l <= g[j].size()+1; l++){
dp[i][k+l] = min(dp[i][k+l]<0?INF:dp[i][k+l], dp[i][k]+dp[j][l]);
}
}
}
}
ll sumt = 0;
for(int i = 0; i < n; i++){
sumt += t[i];
if(dp[0][i+1]>=0){
res = max(res, sum-dp[i][i+1]+sumt);
}
}
cout<<res<<endl;

return 0;
}
```

#### Submission Info

Submission Time 2014-09-27 22:35:58+0900 D - 高橋君と木のおもちゃ Lepton C++ (G++ 4.6.4) 0 1562 Byte WA 451 ms 197160 KB

#### Judge Result

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