在 c++14(GCC 9)并吸氧的情况下,#5跑了1.04s

玄关

记录

#include<bits/stdc++.h>
using namespace std;
int s;
int h[1145],e[1145],ne[1145],idx;
int w[1145],p[1145],cc[1145];
int cnt=2,gen;
int f[1145][6145];
int op;
int a,b,c; 

inline void add()
{
	idx++;
	ne[idx]=h[a];
	e[idx]=b;
	w[idx]=c;
	h[a]=idx;
}

inline int init(int res,int x)
{
	cin>>op;
	if(op==0)
	{
		cc[x]+=init(x,++cnt);
		cc[x]+=init(x,++cnt);
	}
	else
	{
		if(res==x)
		{
			p[x]=op;
			cc[x]=op+op+op+op+op;
		}	
		else
		{
			a=res;
			b=x;
			c=op+op;
			add();
			cc[res]=cc[res]+c;
			init(x,x);
		}
	}
	return cc[x];
}

inline void dfsl(int x)
{
	for(int i=h[x];i;i=ne[i])
	{
		int y=e[i];
		dfsl(y);
		for(int j=cc[x];j>=w[i];--j)
		  for(int k=j;k>=w[i];--k)
		  {
		  	f[x][j]=max(f[x][j],f[x][j-k]+f[y][k-w[i]]);
			}  	
	}
	if(p[x])
	{
		for(int i=1;i<=p[x];++i)
		  f[x][i+i+i+i+i]=i;
	}
		
}



int main()
{
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>s;
	--s;
	cin>>op;
	a=1;
	b=2;
	c=op+op;
	add();
	
	cc[1]=init(1,2);
	
	//dfs(1);
	
	dfsl(1);
	
	/*for(int i=1;i<=cnt;i++)
	  cout<<c[i]<<' ';*/
	  
	cout<<f[1][s];
	
	return 0;
}