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

Submission #242469

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 long long 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], tsz[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 = 0; i <= n; i++){
for(int j = 0;  j <= n; j++){
dp[i][j] = INF;
}
}

for(int i = n-1; i >= 0; i--){
dp[i][0] = 0;
dp[i][1] = s[i];
tsz[i] = 1;
for(int j = 0; j < g[i].size(); j++){
for(int k = 1; k <= tsz[i]; k++){
for(int l = 1; l <= tsz[j]; l++){
dp[i][k+l] = min(dp[i][k+l], dp[i][k]+dp[j][l]);
}
}
tsz[i] += tsz[j];
}
}
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:52:59+0900 D - 高橋君と木のおもちゃ Lepton C++ (G++ 4.6.4) 0 1694 Byte WA 355 ms 196832 KB

#### Judge Result

Score / Max Score 0 / 0 0 / 10 0 / 20 0 / 70
Status
 AC × 1 WA × 1
 AC × 1 WA × 31
 AC × 1 WA × 61
 AC × 1 WA × 91
Set Name Test Cases
Case Name Status Exec Time Memory