QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#55049	#2963. Protect the Pollen!	abdelrahman001	AC ✓	407ms	225472kb	C++	1.3kb	2022-10-12 03:39:24	2022-10-12 03:39:27

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-10-12 03:39:27]
评测

测评结果：AC
用时：407ms
内存：225472kb

查看

[2022-10-12 03:39:24]
提交

answer

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = 3e2 + 5;
int n, S, p[N], s[N];
int memo[N][N][N][2];
vector<int> g[N];
int solve(int node, int par, int j, int rem, bool ok) {
	if(j == g[node].size())
		return 0;
	if(g[node][j] == par)
		return solve(node, par, j + 1, rem, ok);
	int &ans = memo[node][j][rem][ok];
	if(~ans)
		return ans;
	ans = 0;
	for(int i = 0;i <= rem;i++) {
		int leaveChild = solve(g[node][j], node, 0, i, 1);
		int nxt = solve(node, par, j + 1, rem - i, ok);
		ans = max(ans, leaveChild + nxt);
		if(ok && i >= s[g[node][j]]) {
			int takeChild = solve(g[node][j], node, 0, i - s[g[node][j]], 0) + p[g[node][j]];
			ans = max(ans, takeChild + nxt);
		}
	} 
	return ans;
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> S;
    for(int i = 1;i <= n;i++)
		cin >> s[i] >> p[i];
	for(int i = 1;i < n;i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	memset(memo, -1, sizeof memo);
	int ans = solve(1, 1, 0, S, 1);
	if(S >= s[1]) 
		ans = max(ans, solve(1, 1, 0, S - s[1], 0) + p[1]);
	cout << ans;
    return 0;
}

Source code, Language: C++

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 49ms

memory: 225196kb

input:

output:

result:

ok single line: '21'

Test #2:

score: 0

Accepted

time: 32ms

memory: 225364kb

input:

output:

result:

ok single line: '33'

Test #3:

score: 0

Accepted

time: 36ms

memory: 225264kb

input:

output:

result:

ok single line: '0'

Test #4:

score: 0

Accepted

time: 27ms

memory: 225256kb

input:

output:

result:

ok single line: '357'

Test #5:

score: 0

Accepted

time: 24ms

memory: 225340kb

input:

output:

result:

ok single line: '98'

Test #6:

score: 0

Accepted

time: 43ms

memory: 225264kb

input:

output:

result:

ok single line: '0'

Test #7:

score: 0

Accepted

time: 16ms

memory: 225344kb

input:

output:

result:

ok single line: '304'

Test #8:

score: 0

Accepted

time: 16ms

memory: 225368kb

input:

output:

result:

ok single line: '89'

Test #9:

score: 0

Accepted

time: 20ms

memory: 225264kb

input:

output:

result:

ok single line: '0'

Test #10:

score: 0

Accepted

time: 60ms

memory: 225136kb

input:

output:

result:

ok single line: '430'

Test #11:

score: 0

Accepted

time: 25ms

memory: 225280kb

input:

output:

result:

ok single line: '246'

Test #12:

score: 0

Accepted

time: 28ms

memory: 225132kb

input:

output:

result:

ok single line: '0'

Test #13:

score: 0

Accepted

time: 243ms

memory: 225424kb

input:

output:

result:

ok single line: '1119'

Test #14:

score: 0

Accepted

time: 407ms

memory: 225320kb

input:

output:

result:

ok single line: '10545'

Test #15:

score: 0

Accepted

time: 185ms

memory: 225320kb

input:

output:

result:

ok single line: '100'

Test #16:

score: 0

Accepted

time: 244ms

memory: 225276kb

input:

output:

result:

ok single line: '1247'

Test #17:

score: 0

Accepted

time: 393ms

memory: 225288kb

input:

output:

result:

ok single line: '10463'

Test #18:

score: 0

Accepted

time: 238ms

memory: 225288kb

input:

output:

result:

ok single line: '199'

Test #19:

score: 0

Accepted

time: 244ms

memory: 225316kb

input:

output:

result:

ok single line: '1353'

Test #20:

score: 0

Accepted

time: 394ms

memory: 225352kb

input:

output:

result:

ok single line: '15280'

Test #21:

score: 0

Accepted

time: 337ms

memory: 225368kb

input:

output:

result:

ok single line: '986'

Test #22:

score: 0

Accepted

time: 43ms

memory: 225268kb

input:

output:

result:

ok single line: '0'

Test #23:

score: 0

Accepted

time: 20ms

memory: 225272kb

input:

output:

result:

ok single line: '431'

Test #24:

score: 0

Accepted

time: 310ms

memory: 225376kb

input:

output:

result:

ok single line: '5667'

Test #25:

score: 0

Accepted

time: 36ms

memory: 225272kb

input:

1 1
1 42

output:

result:

ok single line: '42'

Test #26:

score: 0

Accepted

time: 32ms

memory: 225432kb

input:

output:

result:

ok single line: '91'

Test #27:

score: 0

Accepted

time: 38ms

memory: 225196kb

input:

output:

result:

ok single line: '139'

Test #28:

score: 0

Accepted

time: 24ms

memory: 225276kb

input:

output:

result:

ok single line: '373'

Test #29:

score: 0

Accepted

time: 28ms

memory: 225192kb

input:

output:

result:

ok single line: '274'

Test #30:

score: 0

Accepted

time: 27ms

memory: 225264kb

input:

output:

result:

ok single line: '100'

Test #31:

score: 0

Accepted

time: 39ms

memory: 225264kb

input:

output:

result:

ok single line: '408'

Test #32:

score: 0

Accepted

time: 36ms

memory: 225252kb

input:

output:

result:

ok single line: '93'

Test #33:

score: 0

Accepted

time: 28ms

memory: 225260kb

input:

output:

result:

ok single line: '142'

Test #34:

score: 0

Accepted

time: 32ms

memory: 225248kb

input:

output:

result:

ok single line: '375'

Test #35:

score: 0

Accepted

time: 39ms

memory: 225312kb

input:

output:

result:

ok single line: '99'

Test #36:

score: 0

Accepted

time: 24ms

memory: 225412kb

input:

output:

result:

ok single line: '89'

Test #37:

score: 0

Accepted

time: 40ms

memory: 225344kb

input:

output:

result:

ok single line: '374'

Test #38:

score: 0

Accepted

time: 32ms

memory: 225308kb

input:

output:

result:

ok single line: '389'

Test #39:

score: 0

Accepted

time: 36ms

memory: 225280kb

input:

output:

result:

ok single line: '217'

Test #40:

score: 0

Accepted

time: 35ms

memory: 225136kb

input:

output:

result:

ok single line: '372'

Test #41:

score: 0

Accepted

time: 28ms

memory: 225412kb

input:

output:

result:

ok single line: '184'

Test #42:

score: 0

Accepted

time: 24ms

memory: 225196kb

input:

output:

result:

ok single line: '253'

Test #43:

score: 0

Accepted

time: 40ms

memory: 225136kb

input:

output:

result:

ok single line: '253'

Test #44:

score: 0

Accepted

time: 19ms

memory: 225192kb

input:

output:

result:

ok single line: '97'

Test #45:

score: 0

Accepted

time: 40ms

memory: 225268kb

input:

output:

result:

ok single line: '252'

Test #46:

score: 0

Accepted

time: 40ms

memory: 225308kb

input:

output:

result:

ok single line: '300'

Test #47:

score: 0

Accepted

time: 28ms

memory: 225204kb

input:

output:

result:

ok single line: '240'

Test #48:

score: 0

Accepted

time: 36ms

memory: 225232kb

input:

output:

result:

ok single line: '173'

Test #49:

score: 0

Accepted

time: 32ms

memory: 225132kb

input:

output:

result:

ok single line: '426'

Test #50:

score: 0

Accepted

time: 31ms

memory: 225196kb

input:

output:

result:

ok single line: '334'

Test #51:

score: 0

Accepted

time: 35ms

memory: 225208kb

input:

output:

result:

ok single line: '126'

Test #52:

score: 0

Accepted

time: 31ms

memory: 225352kb

input:

output:

result:

ok single line: '959'

Test #53:

score: 0

Accepted

time: 31ms

memory: 225200kb

input:

output:

result:

ok single line: '283'

Test #54:

score: 0

Accepted

time: 44ms

memory: 225140kb

input:

output:

result:

ok single line: '89'

Test #55:

score: 0

Accepted

time: 33ms

memory: 225200kb

input:

output:

result:

ok single line: '949'

Test #56:

score: 0

Accepted

time: 52ms

memory: 225252kb

input:

output:

result:

ok single line: '99'

Test #57:

score: 0

Accepted

time: 24ms

memory: 225280kb

input:

output:

result:

ok single line: '0'

Test #58:

score: 0

Accepted

time: 28ms

memory: 225308kb

input:

output:

result:

ok single line: '914'

Test #59:

score: 0

Accepted

time: 55ms

memory: 225368kb

input:

output:

result:

ok single line: '100'

Test #60:

score: 0

Accepted

time: 48ms

memory: 225260kb

input:

output:

result:

ok single line: '161'

Test #61:

score: 0

Accepted

time: 15ms

memory: 225340kb

input:

output:

result:

ok single line: '927'

Test #62:

score: 0

Accepted

time: 20ms

memory: 225272kb

input:

output:

result:

ok single line: '300'

Test #63:

score: 0

Accepted

time: 28ms

memory: 225268kb

input:

output:

result:

ok single line: '562'

Test #64:

score: 0

Accepted

time: 36ms

memory: 225336kb

input:

output:

result:

ok single line: '2803'

Test #65:

score: 0

Accepted

time: 60ms

memory: 225272kb

input:

output:

result:

ok single line: '297'

Test #66:

score: 0

Accepted

time: 44ms

memory: 225328kb

input:

output:

result:

ok single line: '355'

Test #67:

score: 0

Accepted

time: 59ms

memory: 225256kb

input:

output:

result:

ok single line: '3411'

Test #68:

score: 0

Accepted

time: 41ms

memory: 225240kb

input:

output:

result:

ok single line: '296'

Test #69:

score: 0

Accepted

time: 47ms

memory: 225260kb

input:

output:

result:

ok single line: '438'

Test #70:

score: 0

Accepted

time: 48ms

memory: 225216kb

input:

output:

result:

ok single line: '3397'

Test #71:

score: 0

Accepted

time: 24ms

memory: 225136kb

input:

output:

result:

ok single line: '100'

Test #72:

score: 0

Accepted

time: 28ms

memory: 225324kb

input:

output:

result:

ok single line: '495'

Test #73:

score: 0

Accepted

time: 65ms

memory: 225428kb

input:

output:

result:

ok single line: '4870'

Test #74:

score: 0

Accepted

time: 32ms

memory: 225268kb

input:

output:

result:

ok single line: '3799'

Test #75:

score: 0

Accepted

time: 93ms

memory: 225424kb

input:

output:

result:

ok single line: '615'

Test #76:

score: 0

Accepted

time: 152ms

memory: 225324kb

input:

output:

result:

ok single line: '3021'

Test #77:

score: 0

Accepted

time: 92ms

memory: 225336kb

input:

output:

result:

ok single line: '100'

Test #78:

score: 0

Accepted

time: 108ms

memory: 225312kb

input:

output:

result:

ok single line: '1004'

Test #79:

score: 0

Accepted

time: 143ms

memory: 225268kb

input:

output:

result:

ok single line: '3273'

Test #80:

score: 0

Accepted

time: 81ms

memory: 225344kb

input:

output:

result:

ok single line: '100'

Test #81:

score: 0

Accepted

time: 84ms

memory: 225252kb

input:

output:

result:

ok single line: '697'

Test #82:

score: 0

Accepted

time: 162ms

memory: 225236kb

input:

output:

result:

ok single line: '3120'

Test #83:

score: 0

Accepted

time: 104ms

memory: 225268kb

input:

output:

result:

ok single line: '288'

Test #84:

score: 0

Accepted

time: 89ms

memory: 225380kb

input:

output:

result:

ok single line: '774'

Test #85:

score: 0

Accepted

time: 135ms

memory: 225380kb

input:

output:

result:

ok single line: '5020'

Test #86:

score: 0

Accepted

time: 122ms

memory: 225268kb

input:

output:

result:

ok single line: '296'

Test #87:

score: 0

Accepted

time: 32ms

memory: 225384kb

input:

output:

result:

ok single line: '108'

Test #88:

score: 0

Accepted

time: 35ms

memory: 225292kb

input:

output:

result:

ok single line: '988'

Test #89:

score: 0

Accepted

time: 24ms

memory: 225244kb

input:

output:

result:

ok single line: '100'

Test #90:

score: 0

Accepted

time: 28ms

memory: 225208kb

input:

output:

result:

ok single line: '198'

Test #91:

score: 0

Accepted

time: 40ms

memory: 225292kb

input:

output:

result:

ok single line: '975'

Test #92:

score: 0

Accepted

time: 46ms

memory: 225276kb

input:

output:

result:

ok single line: '100'

Test #93:

score: 0

Accepted

time: 15ms

memory: 225260kb

input:

output:

result:

ok single line: '232'

Test #94:

score: 0

Accepted

time: 23ms

memory: 225152kb

input:

output:

result:

ok single line: '973'

Test #95:

score: 0

Accepted

time: 32ms

memory: 225336kb

input:

output:

result:

ok single line: '987'

Test #96:

score: 0

Accepted

time: 4ms

memory: 225408kb

input:

output:

result:

ok single line: '140'

Test #97:

score: 0

Accepted

time: 24ms

memory: 225368kb

input:

output:

result:

ok single line: '991'

Test #98:

score: 0

Accepted

time: 43ms

memory: 225348kb

input:

output:

result:

ok single line: '500'

Test #99:

score: 0

Accepted

time: 44ms

memory: 225200kb

input:

output:

result:

ok single line: '669'

Test #100:

score: 0

Accepted

time: 76ms

memory: 225472kb

input:

output:

result:

ok single line: '7604'

Test #101:

score: 0

Accepted

time: 53ms

memory: 225404kb

input:

output:

result:

ok single line: '300'

Test #102:

score: 0

Accepted

time: 36ms

memory: 225292kb

input:

output:

result:

ok single line: '738'

Test #103:

score: 0

Accepted

time: 67ms

memory: 225292kb

input:

output:

result:

ok single line: '7805'

Test #104:

score: 0

Accepted

time: 52ms

memory: 225144kb

input:

output:

result:

ok single line: '100'

Test #105:

score: 0

Accepted

time: 52ms

memory: 225280kb

input:

output:

result:

ok single line: '964'

Test #106:

score: 0

Accepted

time: 80ms

memory: 225320kb

input:

output:

result:

ok single line: '7980'

Test #107:

score: 0

Accepted

time: 60ms

memory: 225240kb

input:

output:

result:

ok single line: '100'

Test #108:

score: 0

Accepted

time: 48ms

memory: 225240kb

input:

output:

result:

ok single line: '885'

Test #109:

score: 0

Accepted

time: 73ms

memory: 225460kb

input:

output:

result:

ok single line: '8710'

Test #110:

score: 0

Accepted

time: 67ms

memory: 225244kb

input:

output:

result:

ok single line: '786'

Test #111:

score: 0

Accepted

time: 256ms

memory: 225296kb

input:

output:

result:

ok single line: '1728'

Test #112:

score: 0

Accepted

time: 371ms

memory: 225288kb

input:

output:

result:

ok single line: '8720'

Test #113:

score: 0

Accepted

time: 294ms

memory: 225300kb

input:

output:

result:

ok single line: '299'