QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#54993	#2963. Protect the Pollen!	Sa3tElSefr^#	AC ✓	73ms	15064kb	C++	2.4kb	2022-10-11 21:01:02	2022-10-11 21:01:05

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-11 21:01:05]
评测

测评结果：AC
用时：73ms
内存：15064kb

查看

[2022-10-11 21:01:02]
提交

answer

#include <bits/stdc++.h>

#define ll long long
#define ld  double
using namespace std;

// #define int ll

const int N = 300 + 5, mod = 998244353;


int n, total, s[N], power[N];
int dp[N][N][2];

vector<int> adj[N];

vector<int> dpCan[N][N], dpCanT[N][N];


int solveCanTaken(int node, int rem, int idx, int par) {
    if((int) adj[node].size() == idx) return 0;
    if(dpCan[node][rem][idx] != -1) return dpCan[node][rem][idx];

    int child = adj[node][idx];
    if(child == par) return dpCan[node][rem][idx] = solveCanTaken(node, rem, idx + 1, par);

    int ans = 0;
    for(int i = 0; i <= rem; i++) {
        ans = max(ans, dp[child][i][1] + solveCanTaken(node, rem - i, idx + 1, par));
    }
    return dpCan[node][rem][idx] = ans;
}

int solveCanTTaken(int node, int rem, int idx, int par) {
    if((int) adj[node].size() == idx) return 0;
    if(dpCanT[node][rem][idx] != -1) return dpCanT[node][rem][idx];

    int child = adj[node][idx];
    if(child == par) return dpCanT[node][rem][idx] = solveCanTTaken(node, rem, idx + 1, par);

    int ans = 0;
    for(int i = 0; i <= rem; i++) {
        ans = max(ans, dp[child][i][0] + solveCanTTaken(node, rem - i, idx + 1, par));
    }

    return dpCanT[node][rem][idx] = ans;
}


void solve(int node, int par) {
    for(auto i: adj[node]) {
        if(i == par) continue;
        solve(i, node);
    }

    for(int rem = 0; rem <= total; rem++) {
        dp[node][rem][0] = solveCanTaken(node, rem, 0, par);
        dp[node][rem][1] = dp[node][rem][0];
        if(rem >= s[node]) {
            int op2 = power[node] + solveCanTTaken(node, rem - s[node], 0, par);
            dp[node][rem][1] = max(dp[node][rem][1], op2);
        }
    }
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> total;
    for(int i = 1; i <= n; i++) {
        cin >> s[i] >> power[i];
    }

    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= total; j++) {
                dpCan[i][j] = vector<int>((int) adj[i].size(), -1);
                dpCanT[i][j] = dpCan[i][j];
            }
        }


    solve(1, 0);

    int ans = 0;
    for(int i = 0; i <= total; i++) ans = max(ans, dp[1][i][1]);
    cout << ans;




    return 0;
}

源文件, 语言: C++

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 7988kb

input:

output:

result:

ok single line: '21'

Test #2:

score: 0

Accepted

time: 4ms

memory: 7940kb

input:

output:

result:

ok single line: '33'

Test #3:

score: 0

Accepted

time: 1ms

memory: 8032kb

input:

output:

result:

ok single line: '0'

Test #4:

score: 0

Accepted

time: 3ms

memory: 7980kb

input:

output:

result:

ok single line: '357'

Test #5:

score: 0

Accepted

time: 1ms

memory: 7952kb

input:

output:

result:

ok single line: '98'

Test #6:

score: 0

Accepted

time: 0ms

memory: 8024kb

input:

output:

result:

ok single line: '0'

Test #7:

score: 0

Accepted

time: 2ms

memory: 7956kb

input:

output:

result:

ok single line: '304'

Test #8:

score: 0

Accepted

time: 3ms

memory: 8668kb

input:

output:

result:

ok single line: '89'

Test #9:

score: 0

Accepted

time: 1ms

memory: 8012kb

input:

output:

result:

ok single line: '0'

Test #10:

score: 0

Accepted

time: 0ms

memory: 8060kb

input:

output:

result:

ok single line: '430'

Test #11:

score: 0

Accepted

time: 1ms

memory: 8392kb

input:

output:

result:

ok single line: '246'

Test #12:

score: 0

Accepted

time: 1ms

memory: 8096kb

input:

output:

result:

ok single line: '0'

Test #13:

score: 0

Accepted

time: 31ms

memory: 14404kb

input:

output:

result:

ok single line: '1119'

Test #14:

score: 0

Accepted

time: 43ms

memory: 14376kb

input:

output:

result:

ok single line: '10545'

Test #15:

score: 0

Accepted

time: 33ms

memory: 14364kb

input:

output:

result:

ok single line: '100'

Test #16:

score: 0

Accepted

time: 32ms

memory: 14396kb

input:

output:

result:

ok single line: '1247'

Test #17:

score: 0

Accepted

time: 50ms

memory: 14412kb

input:

output:

result:

ok single line: '10463'

Test #18:

score: 0

Accepted

time: 35ms

memory: 14460kb

input:

output:

result:

ok single line: '199'

Test #19:

score: 0

Accepted

time: 48ms

memory: 15064kb

input:

output:

result:

ok single line: '1353'

Test #20:

score: 0

Accepted

time: 73ms

memory: 15040kb

input:

output:

result:

ok single line: '15280'

Test #21:

score: 0

Accepted

time: 60ms

memory: 15004kb

input:

output:

result:

ok single line: '986'

Test #22:

score: 0

Accepted

time: 0ms

memory: 8904kb

input:

output:

result:

ok single line: '0'

Test #23:

score: 0

Accepted

time: 4ms

memory: 8080kb

input:

output:

result:

ok single line: '431'

Test #24:

score: 0

Accepted

time: 34ms

memory: 14412kb

input:

output:

result:

ok single line: '5667'

Test #25:

score: 0

Accepted

time: 1ms

memory: 8044kb

input:

1 1
1 42

output:

result:

ok single line: '42'

Test #26:

score: 0

Accepted

time: 3ms

memory: 8036kb

input:

output:

result:

ok single line: '91'

Test #27:

score: 0

Accepted

time: 2ms

memory: 8076kb

input:

output:

result:

ok single line: '139'

Test #28:

score: 0

Accepted

time: 2ms

memory: 8376kb

input:

output:

result:

ok single line: '373'

Test #29:

score: 0

Accepted

time: 4ms

memory: 8068kb

input:

output:

result:

ok single line: '274'

Test #30:

score: 0

Accepted

time: 0ms

memory: 8332kb

input:

output:

result:

ok single line: '100'

Test #31:

score: 0

Accepted

time: 2ms

memory: 8036kb

input:

output:

result:

ok single line: '408'

Test #32:

score: 0

Accepted

time: 4ms

memory: 8112kb

input:

output:

result:

ok single line: '93'

Test #33:

score: 0

Accepted

time: 3ms

memory: 8076kb

input:

output:

result:

ok single line: '142'

Test #34:

score: 0

Accepted

time: 3ms

memory: 8772kb

input:

output:

result:

ok single line: '375'

Test #35:

score: 0

Accepted

time: 2ms

memory: 8136kb

input:

output:

result:

ok single line: '99'

Test #36:

score: 0

Accepted

time: 3ms

memory: 8016kb

input:

output:

result:

ok single line: '89'

Test #37:

score: 0

Accepted

time: 3ms

memory: 8044kb

input:

output:

result:

ok single line: '374'

Test #38:

score: 0

Accepted

time: 1ms

memory: 8064kb

input:

output:

result:

ok single line: '389'

Test #39:

score: 0

Accepted

time: 1ms

memory: 8248kb

input:

output:

result:

ok single line: '217'

Test #40:

score: 0

Accepted

time: 3ms

memory: 8164kb

input:

output:

result:

ok single line: '372'

Test #41:

score: 0

Accepted

time: 4ms

memory: 8208kb

input:

output:

result:

ok single line: '184'

Test #42:

score: 0

Accepted

time: 5ms

memory: 8072kb

input:

output:

result:

ok single line: '253'

Test #43:

score: 0

Accepted

time: 2ms

memory: 8352kb

input:

output:

result:

ok single line: '253'

Test #44:

score: 0

Accepted

time: 2ms

memory: 8200kb

input:

output:

result:

ok single line: '97'

Test #45:

score: 0

Accepted

time: 4ms

memory: 8740kb

input:

output:

result:

ok single line: '252'

Test #46:

score: 0

Accepted

time: 5ms

memory: 8348kb

input:

output:

result:

ok single line: '300'

Test #47:

score: 0

Accepted

time: 5ms

memory: 8208kb

input:

output:

result:

ok single line: '240'

Test #48:

score: 0

Accepted

time: 1ms

memory: 8412kb

input:

output:

result:

ok single line: '173'

Test #49:

score: 0

Accepted

time: 2ms

memory: 8960kb

input:

output:

result:

ok single line: '426'

Test #50:

score: 0

Accepted

time: 3ms

memory: 8764kb

input:

output:

result:

ok single line: '334'

Test #51:

score: 0

Accepted

time: 4ms

memory: 8268kb

input:

output:

result:

ok single line: '126'

Test #52:

score: 0

Accepted

time: 3ms

memory: 8364kb

input:

output:

result:

ok single line: '959'

Test #53:

score: 0

Accepted

time: 4ms

memory: 8372kb

input:

output:

result:

ok single line: '283'

Test #54:

score: 0

Accepted

time: 4ms

memory: 8444kb

input:

output:

result:

ok single line: '89'

Test #55:

score: 0

Accepted

time: 0ms

memory: 8344kb

input:

output:

result:

ok single line: '949'

Test #56:

score: 0

Accepted

time: 3ms

memory: 8780kb

input:

output:

result:

ok single line: '99'

Test #57:

score: 0

Accepted

time: 1ms

memory: 8400kb

input:

output:

result:

ok single line: '0'

Test #58:

score: 0

Accepted

time: 3ms

memory: 8436kb

input:

output:

result:

ok single line: '914'

Test #59:

score: 0

Accepted

time: 3ms

memory: 8444kb

input:

output:

result:

ok single line: '100'

Test #60:

score: 0

Accepted

time: 3ms

memory: 8352kb

input:

output:

result:

ok single line: '161'

Test #61:

score: 0

Accepted

time: 1ms

memory: 8320kb

input:

output:

result:

ok single line: '927'

Test #62:

score: 0

Accepted

time: 3ms

memory: 8556kb

input:

output:

result:

ok single line: '300'

Test #63:

score: 0

Accepted

time: 5ms

memory: 8740kb

input:

output:

result:

ok single line: '562'

Test #64:

score: 0

Accepted

time: 6ms

memory: 8872kb

input:

output:

result:

ok single line: '2803'

Test #65:

score: 0

Accepted

time: 2ms

memory: 9156kb

input:

output:

result:

ok single line: '297'

Test #66:

score: 0

Accepted

time: 5ms

memory: 8864kb

input:

output:

result:

ok single line: '355'

Test #67:

score: 0

Accepted

time: 2ms

memory: 9160kb

input:

output:

result:

ok single line: '3411'

Test #68:

score: 0

Accepted

time: 5ms

memory: 8812kb

input:

output:

result:

ok single line: '296'

Test #69:

score: 0

Accepted

time: 6ms

memory: 8908kb

input:

output:

result:

ok single line: '438'

Test #70:

score: 0

Accepted

time: 4ms

memory: 8876kb

input:

output:

result:

ok single line: '3397'

Test #71:

score: 0

Accepted

time: 0ms

memory: 8732kb

input:

output:

result:

ok single line: '100'

Test #72:

score: 0

Accepted

time: 2ms

memory: 8932kb

input:

output:

result:

ok single line: '495'

Test #73:

score: 0

Accepted

time: 7ms

memory: 8940kb

input:

output:

result:

ok single line: '4870'

Test #74:

score: 0

Accepted

time: 6ms

memory: 9168kb

input:

output:

result:

ok single line: '3799'

Test #75:

score: 0

Accepted

time: 10ms

memory: 10124kb

input:

output:

result:

ok single line: '615'

Test #76:

score: 0

Accepted

time: 16ms

memory: 10116kb

input:

output:

result:

ok single line: '3021'

Test #77:

score: 0

Accepted

time: 12ms

memory: 10172kb

input:

output:

result:

ok single line: '100'

Test #78:

score: 0

Accepted

time: 14ms

memory: 10104kb

input:

output:

result:

ok single line: '1004'

Test #79:

score: 0

Accepted

time: 12ms

memory: 10100kb

input:

output:

result:

ok single line: '3273'

Test #80:

score: 0

Accepted

time: 9ms

memory: 10412kb

input:

output:

result:

ok single line: '100'

Test #81:

score: 0

Accepted

time: 8ms

memory: 10132kb

input:

output:

result:

ok single line: '697'

Test #82:

score: 0

Accepted

time: 19ms

memory: 10000kb

input:

output:

result:

ok single line: '3120'

Test #83:

score: 0

Accepted

time: 16ms

memory: 10172kb

input:

output:

result:

ok single line: '288'

Test #84:

score: 0

Accepted

time: 16ms

memory: 10332kb

input:

output:

result:

ok single line: '774'

Test #85:

score: 0

Accepted

time: 24ms

memory: 10344kb

input:

output:

result:

ok single line: '5020'

Test #86:

score: 0

Accepted

time: 19ms

memory: 10492kb

input:

output:

result:

ok single line: '296'

Test #87:

score: 0

Accepted

time: 4ms

memory: 9048kb

input:

output:

result:

ok single line: '108'

Test #88:

score: 0

Accepted

time: 4ms

memory: 8920kb

input:

output:

result:

ok single line: '988'

Test #89:

score: 0

Accepted

time: 2ms

memory: 8924kb

input:

output:

result:

ok single line: '100'

Test #90:

score: 0

Accepted

time: 1ms

memory: 8900kb

input:

output:

result:

ok single line: '198'

Test #91:

score: 0

Accepted

time: 4ms

memory: 8880kb

input:

output:

result:

ok single line: '975'

Test #92:

score: 0

Accepted

time: 0ms

memory: 8996kb

input:

output:

result:

ok single line: '100'

Test #93:

score: 0

Accepted

time: 2ms

memory: 8852kb

input:

output:

result:

ok single line: '232'

Test #94:

score: 0

Accepted

time: 4ms

memory: 9000kb

input:

output:

result:

ok single line: '973'

Test #95:

score: 0

Accepted

time: 1ms

memory: 8788kb

input:

output:

result:

ok single line: '987'

Test #96:

score: 0

Accepted

time: 4ms

memory: 9040kb

input:

output:

result:

ok single line: '140'

Test #97:

score: 0

Accepted

time: 1ms

memory: 8928kb

input:

output:

result:

ok single line: '991'

Test #98:

score: 0

Accepted

time: 0ms

memory: 9044kb

input:

output:

result:

ok single line: '500'

Test #99:

score: 0

Accepted

time: 5ms

memory: 10716kb

input:

output:

result:

ok single line: '669'

Test #100:

score: 0

Accepted

time: 6ms

memory: 10800kb

input:

output:

result:

ok single line: '7604'

Test #101:

score: 0

Accepted

time: 7ms

memory: 10624kb

input:

output:

result:

ok single line: '300'

Test #102:

score: 0

Accepted

time: 7ms

memory: 10544kb

input:

output:

result:

ok single line: '738'

Test #103:

score: 0

Accepted

time: 11ms

memory: 10596kb

input:

output:

result:

ok single line: '7805'

Test #104:

score: 0

Accepted

time: 5ms

memory: 10652kb

input:

output:

result:

ok single line: '100'

Test #105:

score: 0

Accepted

time: 9ms

memory: 10708kb

input:

output:

result:

ok single line: '964'

Test #106:

score: 0

Accepted

time: 7ms

memory: 10728kb

input:

output:

result:

ok single line: '7980'

Test #107:

score: 0

Accepted

time: 9ms

memory: 10780kb

input:

output:

result:

ok single line: '100'

Test #108:

score: 0

Accepted

time: 8ms

memory: 10864kb

input:

output:

result:

ok single line: '885'

Test #109:

score: 0

Accepted

time: 10ms

memory: 10860kb

input:

output:

result:

ok single line: '8710'

Test #110:

score: 0

Accepted

time: 8ms

memory: 11008kb

input:

output:

result:

ok single line: '786'

Test #111:

score: 0

Accepted

time: 20ms

memory: 14372kb

input:

output:

result:

ok single line: '1728'

Test #112:

score: 0

Accepted

time: 42ms

memory: 14316kb

input:

output:

result:

ok single line: '8720'

Test #113:

score: 0

Accepted

time: 38ms

memory: 14368kb

input:

output:

result:

ok single line: '299'