Submission #3008823

---

Source Code Expand

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#define llint long long
#define inf (llint)1e18

using namespace std;
typedef pair<llint, llint> P;

struct Item
{
	int id;
	double w, v;
	Item(){}
	Item(int i, double a, double b){
		id = i, w = a, v = b;
	}
	bool operator<(const Item &obj)const{
		double rate = v / w, rate2 = obj.v / obj.w;
		return rate > rate2;
		
	}
};

llint n, x, d;
llint m[55];
vector<int> G[55];
llint W[55], V[55], N[55];
llint remN[55];
vector<llint> wvec, vvec;

llint dp[405][130005];
llint cost[130005];

P dfs(int v)
{
	P ret = make_pair(m[v], 1);
	for(int i = 0; i < G[v].size(); i++){
		P res = dfs(G[v][i]);
		ret.first += res.first;
		ret.second += res.second;
	}
	W[v] = ret.first;
	V[v] = ret.second;
	return ret;
}

void calcDP()
{
	for(int i = 1; i <= n; i++){
		llint useN = min(50LL, N[i]);
		remN[i] = N[i] - useN;
		for(int j = 0; j >= 0; j++){
			llint m = 1<<j;
			if(N[i] <= m) m = N[i], j = -2;
			wvec.push_back(W[i] * m);
			vvec.push_back(V[i] * m);
			N[i] -= m;
		}
	}
	llint num = wvec.size(), mx = n*n*n;
	
	for(int i = 0; i <= num; i++){
		for(int j = 0; j <= mx; j++){
			dp[i][j] = inf;
		}
	}
	dp[0][0] = 0;
	
	for(int i = 0; i < num; i++){
		for(int j = 0; j <= mx; j++){
			if(j + vvec[i] <= mx) dp[i+1][j+vvec[i]] = min(dp[i+1][j+vvec[i]], dp[i][j] + wvec[i]);
			dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
		}
	}
	
	for(int i = 0; i <= mx; i++) cost[i] = dp[num][i];
}

int main(void)
{
	cin >> n >> x >> d;
	cin >> m[1];
	int p;
	for(int i = 2; i <= n; i++){
		cin >> m[i] >> p;
		G[p].push_back(i);
	}
	dfs(1);
	
	N[1] = x;
	for(int i = 2; i <= n; i++) N[i] = d;
	calcDP();
	
	Item item[55];
	for(int i = 1; i <= n; i++){
		item[i] = Item(i, (double)W[i], (double)V[i]);
	}
	sort(item+1, item+n+1);
	
	llint ans = 0;
	for(int i = 0; i <= n*n*n; i++){
		if(cost[i] > x) continue;
		llint remX = x - cost[i], v = i;
		
		for(int j = 1; j <= n; j++){
			llint id = item[j].id;
			llint cap = remX / W[id];
			llint buy = min(cap, remN[id]);
			v += buy * V[id];
			remX -= buy * W[id];
		}
		ans = max(ans, v);
	}
	cout << ans << endl;
	
	return 0;
}

Submission Info

Judge Result