QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#288062	#7966. 采矿	zhouhuanyi	AC ✓	301ms	174236kb	C++20	4.1kb	2023-12-21 17:57:26	2023-12-21 17:57:26

Judging History

你现在查看的是最新测评结果

[2023-12-21 17:57:26]
评测

测评结果：AC
用时：301ms
内存：174236kb

查看

[2023-12-21 17:57:26]
提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 301
using namespace std;
const long long inf=(long long)(1e18);
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
bool cmp(int x,int y)
{
	return x>y;
}
int n,q,s,cnt,opt,fa[N+1],ls[N+1],rs[N+1],r[N+1],p[N+1],tong[N+1],length,tong2[N+1],length2,dfn[N+1],sz[N+1],leng;
long long w[N+1][N+1],w2[N+1][N+1],dp[2][N+1][N+1][N+1],DP[N+1],ans=-inf;
void dfs(int x)
{
	dfn[x]=++leng;
	if (ls[x]) dfs(ls[x]);
	if (rs[x]) dfs(rs[x]);
	sz[x]=sz[ls[x]]+sz[rs[x]]+1;
	return;
}
void dfs2(int x)
{
	if (ls[x]) dfs2(ls[x]);
	if (rs[x]) dfs2(rs[x]);
	if (ls[x])
	{
		for (int i=0;i<=sz[ls[x]];++i) DP[i]=-inf;
		for (int i=0;i<=sz[ls[ls[x]]];++i)
			for (int j=0;j<=sz[rs[ls[x]]];++j)
				DP[i+j]=max(DP[i+j],max(dp[opt^1][ls[x]][i][j],dp[opt][ls[x]][i][j]));
		for (int i=0;i<=sz[ls[x]];++i)
			for (int j=0;j<=sz[rs[x]];++j)
				dp[opt][x][i][j]=max(dp[opt][x][i][j],DP[i]);
	}
	if (rs[x])
	{
		for (int i=0;i<=sz[rs[x]];++i) DP[i]=-inf;
		for (int i=0;i<=sz[ls[rs[x]]];++i)
			for (int j=0;j<=sz[rs[rs[x]]];++j)
				DP[i+j]=max(DP[i+j],max(dp[opt^1][rs[x]][i][j],dp[opt][rs[x]][i][j]));
		for (int i=0;i<=sz[ls[x]];++i)
			for (int j=0;j<=sz[rs[x]];++j)
				dp[opt][x][i][j]=max(dp[opt][x][i][j],DP[j]);
	}
	return;
}
void dfs3(int x)
{
	if (ls[x])
	{
		for (int i=0;i<=sz[ls[x]];++i) DP[i]=-inf;
		for (int i=0;i<=sz[ls[x]];++i)
			for (int j=0;j<=sz[rs[x]];++j)
				DP[i]=max(DP[i],max(dp[opt^1][x][i][j],dp[opt][x][i][j]));
		for (int i=0;i<=sz[ls[ls[x]]];++i)
			for (int j=0;j<=sz[rs[ls[x]]];++j)
				dp[opt][ls[x]][i][j]=max(dp[opt][ls[x]][i][j],DP[i+j]);
	}
	if (rs[x])
	{
		for (int i=0;i<=sz[rs[x]];++i) DP[i]=-inf;
		for (int i=0;i<=sz[ls[x]];++i)
			for (int j=0;j<=sz[rs[x]];++j)
				DP[j]=max(DP[j],max(dp[opt^1][x][i][j],dp[opt][x][i][j]));
		for (int i=0;i<=sz[ls[rs[x]]];++i)
			for (int j=0;j<=sz[rs[rs[x]]];++j)
				dp[opt][rs[x]][i][j]=max(dp[opt][rs[x]][i][j],DP[i+j]);
	}
	if (ls[x]) dfs3(ls[x]);
	if (rs[x]) dfs3(rs[x]);
	return;
}
bool LENG(int x,int y)
{
	return dfn[x]<=dfn[y]&&dfn[y]<=dfn[x]+sz[x]-1;
}
int main()
{
	int op;
	n=read(),q=read(),s=read();
	for (int i=2;i<=n;++i)
	{
		fa[i]=read();
		if (!ls[fa[i]]) ls[fa[i]]=i;
		else rs[fa[i]]=i;
	}
	for (int i=2;i<=n;++i) r[i]=read();
	for (int i=2;i<=n;++i) p[i]=read();
	dfs(1);
	for (int i=1;i<=n;++i)
	{
		length=length2=0;
		for (int j=1;j<=n;++j)
		{
			if (LENG(i,j)) tong[++length]=p[j];
			else tong2[++length2]=p[j];
		}
		sort(tong+1,tong+length+1,cmp),sort(tong2+1,tong2+length2+1,cmp);
		for (int j=1;j<=length;++j) w[i][j]=w[i][j-1]+tong[j];
		for (int j=1;j<=length2;++j) w2[i][j]=w2[i][j-1]+tong2[j];
	}
	for (int i=1;i<=n;++i)
		for (int j=0;j<=sz[ls[i]];++j)
			for (int k=0;k<=sz[rs[i]];++k)
				dp[0][i][j][k]=-inf;
	dp[0][s][0][0]=0;
	for (int i=1;i<=q;++i)
	{
		opt^=1;
		for (int j=1;j<=n;++j)
			for (int k=0;k<=sz[ls[j]];++k)
				for (int t=0;t<=sz[rs[j]];++t)
					dp[opt][j][k][t]=-inf;
		op=read();
		if (op==1) dfs2(1);
		else if (op==2) dfs3(1);
		else if (op==3)
		{
			for (int j=1;j<=n;++j)
				for (int k=0;k<=sz[ls[j]];++k)
					for (int t=0;t<=sz[rs[j]];++t)
						dp[opt][j][k][t]=dp[opt^1][j][k][t];
			cnt++;
		}
		else
		{
			cnt--;
			for (int j=1;j<=n;++j)
				for (int k=0;k<=sz[ls[j]];++k)
					for (int t=0;t<=sz[rs[j]];++t)
						dp[opt][j][k][t]=dp[opt^1][j][k][t];
			if (cnt<0)
			{
				puts("No solution.");
				return 0;
			}
		}
		for (int j=1;j<=n;++j)
			for (int k=0;k<=sz[ls[j]];++k)
				for (int t=0;t<=sz[rs[j]];++t)
					if (dp[opt][j][k][t]>=0)
					{
						if (cnt-k-t<0||cnt-k-t>n-sz[j]) dp[opt][j][k][t]=-inf;
						else dp[opt][j][k][t]+=r[j]+w[ls[j]][k]+w[rs[j]][t]+w2[j][cnt-k-t];
					}
	}
	for (int i=1;i<=n;++i)
		for (int j=0;j<=sz[ls[i]];++j)
			for (int k=0;k<=sz[rs[i]];++k)
				ans=max(ans,dp[opt][i][j][k]);
	if (ans<0) puts("No solution.");
	else printf("%lld\n",ans);
	return 0;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 79ms

memory: 119792kb

input:

300 600 175
1 2 1 4 4 2 7 8 9 8 3 5 12 10 6 6 13 15 9 11 11 13 15 22 14 26 27 12 5 16 10 24 23 16 33 34 21 22 37 39 17 39 40 20 36 28 40 33 48 29 26 46 46 18 37 32 20 38 54 45 19 30 52 27 18 60 41 57 30 50 48 47 65 17 35 14 55 24 78 80 71 81 28 3 21 19 63 35 75 75 73 92 89 36 81 50 34 93 85 43 42 78...

output:

4588927051034

result:

ok single line: '4588927051034'

Test #2:

score: 0

Accepted

time: 78ms

memory: 99336kb

input:

300 600 286
1 1 3 3 5 6 6 7 7 9 2 2 9 10 5 13 11 12 8 15 20 22 11 15 21 16 4 26 19 20 25 27 10 23 13 12 32 32 8 26 18 19 28 42 4 46 41 37 23 43 30 25 34 47 49 22 40 48 28 45 16 35 35 63 55 33 44 61 21 56 61 59 63 65 73 47 42 51 62 76 48 59 39 66 58 77 57 73 68 27 29 53 85 83 56 41 60 69 74 58 100 10...

output:

40349159313289

result:

ok single line: '40349159313289'

Test #3:

score: 0

Accepted

time: 301ms

memory: 174236kb

input:

301 600 153
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...

output:

44810792039851

result:

ok single line: '44810792039851'

Test #4:

score: 0

Accepted

time: 106ms

memory: 137564kb

input:

300 600 264
1 1 2 2 3 6 6 7 9 10 10 12 5 11 15 12 11 14 16 14 17 17 16 21 25 19 27 28 26 28 24 29 33 31 35 34 31 30 32 39 33 39 37 43 44 46 42 46 43 49 45 45 47 48 51 47 56 57 54 57 59 53 58 56 58 59 61 60 68 65 67 68 70 69 67 69 70 73 72 80 76 76 82 78 77 77 87 87 82 90 85 85 91 86 95 93 96 96 91 9...

output:

52315813623226

result:

ok single line: '52315813623226'

Test #5:

score: 0

Accepted

time: 129ms

memory: 134312kb

input:

300 600 33
1 1 2 4 4 2 5 5 9 9 8 11 10 12 13 13 15 11 18 19 18 16 19 22 17 22 21 23 28 25 29 27 29 34 28 30 31 36 38 34 39 39 35 44 36 42 38 45 41 45 43 52 44 52 51 48 55 56 55 56 60 57 54 60 58 66 59 63 63 61 68 67 68 65 72 71 74 76 72 80 73 74 83 81 82 81 79 87 86 85 91 86 88 88 94 89 90 94 98 97 ...

output:

48722943497148

result:

ok single line: '48722943497148'

Test #6:

score: 0

Accepted

time: 111ms

memory: 132984kb

input:

300 600 42
1 1 3 4 2 2 5 8 8 9 6 9 11 13 11 12 15 12 10 19 15 19 21 18 16 25 18 21 28 28 23 29 27 34 26 27 31 33 30 32 37 34 39 43 42 45 39 40 40 45 51 50 50 51 52 52 54 58 55 57 59 60 54 62 65 66 66 67 60 63 62 63 73 73 68 76 76 71 71 77 81 78 82 79 84 79 84 83 87 87 85 91 92 89 94 93 90 95 99 95 9...

output:

55427849622319

result:

ok single line: '55427849622319'

Test #7:

score: 0

Accepted

time: 113ms

memory: 132888kb

input:

300 600 137
1 2 1 3 2 6 7 6 4 8 11 5 11 5 13 12 10 10 12 17 13 18 22 18 21 20 20 23 23 27 27 29 25 29 33 35 36 31 33 35 40 40 43 44 39 43 41 46 42 46 49 44 53 52 55 54 51 55 51 59 56 61 54 62 61 59 64 62 60 68 67 63 65 73 72 73 72 75 74 79 77 80 78 76 77 83 78 80 88 89 86 90 89 91 90 93 92 97 95 95 ...

output:

53287628221118

result:

ok single line: '53287628221118'

Test #8:

score: 0

Accepted

time: 115ms

memory: 135464kb

input:

300 600 70
1 1 2 2 3 3 5 6 9 8 9 10 13 8 6 12 16 12 17 16 20 20 21 23 23 21 22 27 22 28 25 31 25 33 34 33 37 38 34 35 35 38 36 43 39 39 45 40 41 42 43 44 52 54 47 50 57 53 51 56 56 53 60 63 61 65 58 66 61 68 62 65 69 73 72 68 72 78 76 79 74 76 82 81 84 77 84 88 85 85 82 91 86 92 89 92 91 95 98 99 96...

output:

52245066034805

result:

ok single line: '52245066034805'

Test #9:

score: 0

Accepted

time: 102ms

memory: 127596kb

input:

300 600 56
1 2 2 4 3 6 1 7 7 6 5 11 8 12 12 10 9 14 13 11 14 13 18 21 20 25 18 21 20 27 24 32 32 33 29 30 28 30 37 40 33 36 34 38 41 38 47 48 44 43 48 51 53 50 49 56 52 56 55 52 57 54 60 63 61 60 61 68 65 70 63 66 70 69 67 72 77 77 72 73 80 78 81 81 80 78 82 88 88 89 90 89 90 91 86 87 97 91 93 97 94...

output:

54169471106772

result:

ok single line: '54169471106772'

Test #10:

score: 0

Accepted

time: 128ms

memory: 126796kb

input:

300 600 105
1 1 3 3 2 6 4 2 8 5 9 6 10 14 7 12 13 9 17 14 12 20 21 19 22 22 24 27 23 30 28 29 32 34 32 33 30 33 35 31 38 38 35 43 36 39 44 44 43 46 50 50 45 53 48 52 56 57 52 54 53 59 55 59 64 62 66 60 60 66 70 63 70 71 72 74 77 78 72 76 75 81 80 82 80 85 79 79 89 89 83 90 91 94 86 88 97 95 95 94 10...

output:

50990422314888

result:

ok single line: '50990422314888'

Test #11:

score: 0

Accepted

time: 109ms

memory: 144196kb

input:

300 600 99
1 2 3 1 3 5 6 6 2 8 11 10 9 13 10 14 13 16 17 17 19 19 20 15 21 18 18 27 29 28 23 29 30 34 31 35 32 31 37 40 34 40 42 42 39 38 47 48 43 47 51 46 49 50 51 48 49 58 50 54 52 62 60 57 63 63 64 68 62 66 70 67 69 71 66 74 71 76 76 77 81 75 81 77 85 84 82 85 89 86 82 87 92 94 86 96 90 97 90 96 ...

output:

50233132966129

result:

ok single line: '50233132966129'

Test #12:

score: 0

Accepted

time: 78ms

memory: 130140kb

input:

300 600 57
1 1 3 4 4 5 7 8 6 8 9 10 3 5 12 11 13 16 12 15 19 11 17 17 19 25 14 2 29 10 9 32 28 29 32 33 34 7 16 36 25 27 38 38 6 26 18 42 27 49 36 20 28 43 20 14 37 18 34 24 53 2 31 53 31 33 54 40 30 41 57 44 64 46 42 71 60 51 59 45 49 21 54 47 47 75 69 45 24 23 80 87 86 75 95 92 70 48 55 95 56 90 6...

output:

4351680767374

result:

ok single line: '4351680767374'

Test #13:

score: 0

Accepted

time: 103ms

memory: 132628kb

input:

300 600 111
1 2 1 4 3 6 5 8 7 5 10 12 7 11 6 14 17 12 13 13 20 14 21 23 17 18 23 20 29 28 22 30 28 34 34 31 35 29 31 32 36 37 40 37 39 43 43 41 40 49 44 46 44 48 49 48 53 55 53 51 52 62 59 55 63 66 60 65 65 70 67 69 66 71 73 67 73 77 76 72 72 80 77 83 82 84 84 82 88 90 83 87 88 87 93 96 92 93 98 98 ...

output:

50231080085638

result:

ok single line: '50231080085638'

Test #14:

score: 0

Accepted

time: 100ms

memory: 134604kb

input:

300 600 202
1 1 3 4 3 2 7 6 2 10 10 11 5 8 7 12 8 11 18 17 18 17 20 22 20 21 24 26 27 23 28 31 28 30 26 30 29 32 38 36 35 38 40 36 40 46 43 45 45 46 47 49 48 50 52 51 56 53 50 56 60 57 58 64 65 64 59 60 68 63 70 63 73 73 75 76 71 75 78 77 81 76 83 84 78 85 81 86 82 82 83 92 90 94 90 96 91 93 94 91 9...

output:

47868585292289

result:

ok single line: '47868585292289'

Test #15:

score: 0

Accepted

time: 61ms

memory: 116312kb

input:

301 600 150
1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19 21 21 23 23 25 25 27 27 29 29 31 31 33 33 35 35 37 37 39 39 41 41 43 43 45 45 47 47 49 49 51 51 53 53 55 55 57 57 59 59 61 61 63 63 65 65 67 67 69 69 71 71 73 73 75 75 77 77 79 79 81 81 83 83 85 85 87 87 89 89 91 91 93 93 95 95 97 97 99 9...

output:

1557184330900

result:

ok single line: '1557184330900'

Test #16:

score: 0

Accepted

time: 75ms

memory: 124404kb

input:

300 600 191
1 2 3 2 4 4 6 6 8 9 3 7 13 7 13 11 14 12 15 15 21 16 14 22 25 22 24 23 21 26 28 27 28 33 30 33 32 36 30 31 32 35 37 43 40 45 39 40 41 41 48 46 46 54 53 55 57 49 50 59 60 59 61 57 61 65 66 64 63 63 64 66 71 73 74 69 71 74 76 79 76 79 81 78 85 86 83 87 83 87 86 84 90 92 91 96 90 93 92 91 9...

output:

No solution.

result:

ok single line: 'No solution.'

Test #17:

score: 0

Accepted

time: 87ms

memory: 145876kb

input:

300 600 189
1 2 2 4 4 1 5 5 8 7 11 12 12 7 15 15 8 18 10 13 21 20 22 16 21 22 20 19 24 23 30 28 29 34 29 30 37 38 38 36 32 42 34 35 41 40 39 40 47 48 45 49 48 53 49 47 55 57 53 51 56 54 59 64 56 59 64 65 62 62 66 71 70 66 70 67 69 73 77 77 76 73 80 84 81 79 87 79 83 84 85 83 87 94 94 93 88 97 90 92 ...

output:

No solution.

result:

ok single line: 'No solution.'

Test #18:

score: 0

Accepted

time: 63ms

memory: 133148kb

input:

300 600 271
1 2 2 4 4 5 1 8 9 5 11 3 12 7 11 7 16 9 19 19 16 8 3 24 25 25 27 14 10 15 17 15 32 20 29 26 26 28 23 33 23 28 41 35 27 44 32 47 17 44 6 50 52 35 54 10 45 55 43 52 13 21 46 42 20 42 47 60 64 67 39 21 57 56 63 55 71 18 22 54 43 57 34 56 36 51 59 68 53 59 74 34 76 69 94 48 13 41 53 64 12 18...

output:

No solution.

result:

ok single line: 'No solution.'

Test #19:

score: 0

Accepted

time: 71ms

memory: 114648kb

input:

300 600 64
1 1 3 3 2 5 5 8 8 9 6 12 4 12 15 14 16 16 14 2 13 18 6 15 7 13 18 22 20 10 24 31 20 26 26 31 32 33 37 24 36 37 10 27 33 7 42 44 22 38 38 9 49 32 55 53 21 19 57 35 43 55 51 21 34 62 17 43 48 68 53 47 65 69 50 72 70 47 25 40 67 50 39 77 45 60 36 81 29 65 58 41 41 63 72 60 83 56 97 19 68 90 ...

output:

No solution.

result:

ok single line: 'No solution.'

Test #20:

score: 0

Accepted

time: 31ms

memory: 129392kb

input:

300 600 170
1 2 3 2 1 6 7 4 7 4 10 9 5 10 11 9 5 17 17 16 3 19 20 8 13 8 20 12 19 22 28 28 29 14 22 11 29 25 14 6 13 40 36 35 45 18 37 12 47 31 15 26 25 41 49 26 31 53 53 34 21 45 23 42 58 47 61 66 59 39 61 66 44 21 48 75 50 27 77 48 77 56 60 75 63 62 86 84 67 71 38 51 81 30 37 85 89 80 87 36 78 52 ...

output:

No solution.

result:

ok single line: 'No solution.'

Test #21:

score: 0

Accepted

time: 81ms

memory: 127828kb

input:

300 600 214
1 1 3 3 5 5 4 4 9 10 7 9 13 11 7 8 15 10 16 11 18 17 22 23 12 18 16 25 23 24 12 15 24 14 21 31 36 21 17 39 39 36 30 20 32 26 45 38 46 8 49 22 30 28 33 49 50 58 27 44 32 46 58 44 37 48 38 28 43 13 62 66 31 14 35 63 74 34 68 25 42 26 76 76 19 41 85 56 29 78 63 61 82 59 64 6 62 65 97 43 51 ...

output:

4485712836520

result:

ok single line: '4485712836520'

Test #22:

score: 0

Accepted

time: 2ms

memory: 11996kb

input:

6 3 2
1 2 3 3 2
45 38 27 44 79
5 3 5 5 9
1
2
3

output:

result:

ok single line: '163'

Test #23:

score: 0

Accepted

time: 79ms

memory: 121424kb

input:

300 600 296
1 1 3 4 4 5 7 7 6 3 5 12 12 13 2 10 13 2 8 20 15 21 16 16 24 24 8 26 18 22 18 27 21 34 10 34 20 38 25 38 28 36 28 22 6 40 40 42 15 44 44 29 29 9 41 50 57 43 50 57 42 32 62 46 14 60 56 9 41 30 71 60 63 54 48 65 73 74 14 27 63 72 25 66 56 71 43 23 32 70 83 48 88 49 26 47 85 53 39 23 45 98 ...

output:

4411111707253

result:

ok single line: '4411111707253'

Test #24:

score: 0

Accepted

time: 80ms

memory: 123976kb

input:

300 600 110
1 1 2 3 2 4 6 3 6 10 7 7 13 4 8 9 11 14 15 9 15 19 13 5 21 5 8 11 23 18 10 26 22 23 16 30 34 20 20 22 34 36 33 31 16 21 40 19 17 43 31 35 14 35 12 12 30 26 50 51 59 59 56 43 44 55 18 48 46 29 62 28 28 44 50 25 65 71 74 77 61 55 25 39 80 84 71 74 62 80 63 48 67 17 69 76 87 38 82 83 27 51 ...

output:

4479248027267

result:

ok single line: '4479248027267'

Test #25:

score: 0

Accepted

time: 85ms

memory: 128216kb

input:

300 600 254
1 2 1 3 2 6 3 7 8 10 9 5 4 12 5 16 6 13 13 4 18 10 11 14 8 23 7 16 22 18 15 26 25 31 19 11 29 29 35 20 41 42 14 25 23 35 33 24 36 33 27 15 40 48 41 39 39 46 19 12 36 51 34 37 61 58 22 58 42 64 32 20 28 9 72 60 76 49 46 70 47 61 69 80 45 69 76 79 44 90 86 34 77 60 71 48 64 66 43 86 92 53 ...

output:

4532069466798

result:

ok single line: '4532069466798'

Test #26:

score: 0

Accepted

time: 73ms

memory: 128256kb

input:

300 600 274
1 1 2 4 3 4 2 7 9 7 11 9 10 3 8 16 5 17 16 10 5 14 23 22 24 25 24 27 28 11 8 22 27 6 12 18 20 12 6 23 15 41 26 34 29 20 37 14 18 41 35 37 31 43 29 32 15 26 47 42 19 32 17 35 21 30 65 68 36 28 49 13 70 58 49 65 75 55 61 47 54 55 82 46 58 60 68 73 39 64 25 75 50 31 45 50 66 97 73 53 82 94 ...

output:

37149511717824

result:

ok single line: '37149511717824'

Test #27:

score: 0

Accepted

time: 72ms

memory: 127628kb

input:

300 600 262
1 2 1 4 5 5 3 7 7 6 11 8 3 11 2 16 9 17 8 19 12 13 20 14 9 6 4 16 17 24 29 30 32 15 23 18 23 19 33 21 31 12 36 29 44 36 41 45 31 18 33 25 35 39 46 50 46 52 35 38 52 61 32 39 59 27 30 57 63 43 56 28 45 50 63 74 64 61 71 79 56 60 69 27 13 20 87 28 76 10 82 75 15 21 24 70 43 94 58 75 69 55 ...

output:

38295501087283

result:

ok single line: '38295501087283'