QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#55965	#2963. Protect the Pollen!	MahmoudAtia	AC ✓	229ms	5260kb	C++	2.5kb	2022-10-16 02:51:13	2022-10-16 02:51:15

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-16 02:51:15]
评测

测评结果：AC
用时：229ms
内存：5260kb

查看

[2022-10-16 02:51:13]
提交

answer

#include <bits/stdc++.h>

typedef long double ld;
typedef long long ll;
using namespace std;
int di[] = {1, 0, -1, -1, 0, 1, -1, 1};
int dj[] = {1, 1, 0, -1, -1, 0, 1, -1};
const ll oo = 1e18, MOD = 998244353;
const int N = 305, M = 1e6 + 5;
const ld PI = acos(-1.0), EPS = 1e-9;

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int dp[N][N][2][2], k, n, s[N], p[N], pos[N], par[N];
vector<int> v2[N], v[N];

void dfs(int node, int par) {
    for (auto x:v2[node]) {
        if (x != par) {
            v[node].push_back(x);
            dfs(x, node);
        }
    }
}

void init() {
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < v[i].size(); j++) pos[v[i][j]] = j, par[v[i][j]] = i;
    }
}

int solve(int node, int rem, int me, int valid) {
    if (v[node].size() == 0 && me) {
        if (valid && s[node] <= rem) return p[node];
        else return 0;
    }
    int &ret = dp[node][rem][me][valid];
    if (~ret) return ret;
    ret = 0;
    if (me) {
        for (int i = 0; i <= rem; i++) {
            int tmp = solve(v[node][0], i, 1, 1);
            if (v[node].size() > 1) tmp += solve(v[node][1], rem - i, 0, 1);
            ret = max(ret, tmp);
        }
        if (s[node] <= rem && valid) {
            for (int i = 0; i <= rem - s[node]; i++) {
                int tmp = solve(v[node][0], i, 1, 0);
                if (v[node].size() > 1) tmp += solve(v[node][1], rem - s[node] - i, 0, 0);
                ret = max(ret, tmp + p[node]);
            }
        }
    } else {
        for (int i = 0; i <= rem; i++) {
            int tmp = solve(v[par[node]][pos[node]], i, 1, valid);
            if (v[par[node]].size() > pos[node] + 1)
                tmp += solve(v[par[node]][pos[node] + 1], rem - i, 0, valid);
            ret = max(ret, tmp);
        }
    }
    return ret;
}

//#define endl '\n'
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //freopen("farm.in", "r", stdin);
    memset(dp, -1, sizeof dp);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> s[i] >> p[i];
    for (int i = 2; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        v2[x].push_back(y);
        v2[y].push_back(x);
    }
    dfs(1, 1);
    init();
    cout << solve(1, k, 1, 1);
    return 0;
}

源文件, 语言: C++

詳細信息

Test #1:

score: 100

Accepted

time: 3ms

memory: 5176kb

input:

output:

result:

ok single line: '21'

Test #2:

score: 0

Accepted

time: 3ms

memory: 5136kb

input:

output:

result:

ok single line: '33'

Test #3:

score: 0

Accepted

time: 3ms

memory: 5224kb

input:

output:

result:

ok single line: '0'

Test #4:

score: 0

Accepted

time: 2ms

memory: 5084kb

input:

output:

result:

ok single line: '357'

Test #5:

score: 0

Accepted

time: 3ms

memory: 5176kb

input:

output:

result:

ok single line: '98'

Test #6:

score: 0

Accepted

time: 2ms

memory: 5060kb

input:

output:

result:

ok single line: '0'

Test #7:

score: 0

Accepted

time: 2ms

memory: 5176kb

input:

output:

result:

ok single line: '304'

Test #8:

score: 0

Accepted

time: 3ms

memory: 5112kb

input:

output:

result:

ok single line: '89'

Test #9:

score: 0

Accepted

time: 3ms

memory: 5112kb

input:

output:

result:

ok single line: '0'

Test #10:

score: 0

Accepted

time: 3ms

memory: 5236kb

input:

output:

result:

ok single line: '430'

Test #11:

score: 0

Accepted

time: 3ms

memory: 5008kb

input:

output:

result:

ok single line: '246'

Test #12:

score: 0

Accepted

time: 1ms

memory: 5040kb

input:

output:

result:

ok single line: '0'

Test #13:

score: 0

Accepted

time: 124ms

memory: 5020kb

input:

output:

result:

ok single line: '1119'

Test #14:

score: 0

Accepted

time: 215ms

memory: 5148kb

input:

output:

result:

ok single line: '10545'

Test #15:

score: 0

Accepted

time: 95ms

memory: 5240kb

input:

output:

result:

ok single line: '100'

Test #16:

score: 0

Accepted

time: 129ms

memory: 5240kb

input:

output:

result:

ok single line: '1247'

Test #17:

score: 0

Accepted

time: 209ms

memory: 5100kb

input:

output:

result:

ok single line: '10463'

Test #18:

score: 0

Accepted

time: 124ms

memory: 5236kb

input:

output:

result:

ok single line: '199'

Test #19:

score: 0

Accepted

time: 144ms

memory: 5112kb

input:

output:

result:

ok single line: '1353'

Test #20:

score: 0

Accepted

time: 229ms

memory: 5136kb

input:

output:

result:

ok single line: '15280'

Test #21:

score: 0

Accepted

time: 218ms

memory: 5136kb

input:

output:

result:

ok single line: '986'

Test #22:

score: 0

Accepted

time: 6ms

memory: 5184kb

input:

output:

result:

ok single line: '0'

Test #23:

score: 0

Accepted

time: 3ms

memory: 5120kb

input:

output:

result:

ok single line: '431'

Test #24:

score: 0

Accepted

time: 174ms

memory: 5096kb

input:

output:

result:

ok single line: '5667'

Test #25:

score: 0

Accepted

time: 3ms

memory: 5088kb

input:

1 1
1 42

output:

result:

ok single line: '42'

Test #26:

score: 0

Accepted

time: 3ms

memory: 5136kb

input:

output:

result:

ok single line: '91'

Test #27:

score: 0

Accepted

time: 2ms

memory: 5056kb

input:

output:

result:

ok single line: '139'

Test #28:

score: 0

Accepted

time: 3ms

memory: 5132kb

input:

output:

result:

ok single line: '373'

Test #29:

score: 0

Accepted

time: 3ms

memory: 5120kb

input:

output:

result:

ok single line: '274'

Test #30:

score: 0

Accepted

time: 3ms

memory: 5120kb

input:

output:

result:

ok single line: '100'

Test #31:

score: 0

Accepted

time: 2ms

memory: 5068kb

input:

output:

result:

ok single line: '408'

Test #32:

score: 0

Accepted

time: 3ms

memory: 5076kb

input:

output:

result:

ok single line: '93'

Test #33:

score: 0

Accepted

time: 3ms

memory: 5004kb

input:

output:

result:

ok single line: '142'

Test #34:

score: 0

Accepted

time: 3ms

memory: 5036kb

input:

output:

result:

ok single line: '375'

Test #35:

score: 0

Accepted

time: 3ms

memory: 5076kb

input:

output:

result:

ok single line: '99'

Test #36:

score: 0

Accepted

time: 1ms

memory: 5220kb

input:

output:

result:

ok single line: '89'

Test #37:

score: 0

Accepted

time: 1ms

memory: 5072kb

input:

output:

result:

ok single line: '374'

Test #38:

score: 0

Accepted

time: 1ms

memory: 4940kb

input:

output:

result:

ok single line: '389'

Test #39:

score: 0

Accepted

time: 5ms

memory: 5116kb

input:

output:

result:

ok single line: '217'

Test #40:

score: 0

Accepted

time: 3ms

memory: 5004kb

input:

output:

result:

ok single line: '372'

Test #41:

score: 0

Accepted

time: 2ms

memory: 5172kb

input:

output:

result:

ok single line: '184'

Test #42:

score: 0

Accepted

time: 6ms

memory: 5176kb

input:

output:

result:

ok single line: '253'

Test #43:

score: 0

Accepted

time: 8ms

memory: 5040kb

input:

output:

result:

ok single line: '253'

Test #44:

score: 0

Accepted

time: 0ms

memory: 5076kb

input:

output:

result:

ok single line: '97'

Test #45:

score: 0

Accepted

time: 3ms

memory: 5076kb

input:

output:

result:

ok single line: '252'

Test #46:

score: 0

Accepted

time: 7ms

memory: 4944kb

input:

output:

result:

ok single line: '300'

Test #47:

score: 0

Accepted

time: 2ms

memory: 5148kb

input:

output:

result:

ok single line: '240'

Test #48:

score: 0

Accepted

time: 3ms

memory: 5008kb

input:

output:

result:

ok single line: '173'

Test #49:

score: 0

Accepted

time: 9ms

memory: 5088kb

input:

output:

result:

ok single line: '426'

Test #50:

score: 0

Accepted

time: 8ms

memory: 5092kb

input:

output:

result:

ok single line: '334'

Test #51:

score: 0

Accepted

time: 3ms

memory: 5092kb

input:

output:

result:

ok single line: '126'

Test #52:

score: 0

Accepted

time: 3ms

memory: 5240kb

input:

output:

result:

ok single line: '959'

Test #53:

score: 0

Accepted

time: 2ms

memory: 5016kb

input:

output:

result:

ok single line: '283'

Test #54:

score: 0

Accepted

time: 3ms

memory: 4952kb

input:

output:

result:

ok single line: '89'

Test #55:

score: 0

Accepted

time: 3ms

memory: 5048kb

input:

output:

result:

ok single line: '949'

Test #56:

score: 0

Accepted

time: 3ms

memory: 4952kb

input:

output:

result:

ok single line: '99'

Test #57:

score: 0

Accepted

time: 2ms

memory: 4952kb

input:

output:

result:

ok single line: '0'

Test #58:

score: 0

Accepted

time: 3ms

memory: 5124kb

input:

output:

result:

ok single line: '914'

Test #59:

score: 0

Accepted

time: 3ms

memory: 5172kb

input:

output:

result:

ok single line: '100'

Test #60:

score: 0

Accepted

time: 3ms

memory: 5028kb

input:

output:

result:

ok single line: '161'

Test #61:

score: 0

Accepted

time: 3ms

memory: 5164kb

input:

output:

result:

ok single line: '927'

Test #62:

score: 0

Accepted

time: 3ms

memory: 5076kb

input:

output:

result:

ok single line: '300'

Test #63:

score: 0

Accepted

time: 2ms

memory: 5132kb

input:

output:

result:

ok single line: '562'

Test #64:

score: 0

Accepted

time: 9ms

memory: 5120kb

input:

output:

result:

ok single line: '2803'

Test #65:

score: 0

Accepted

time: 3ms

memory: 5188kb

input:

output:

result:

ok single line: '297'

Test #66:

score: 0

Accepted

time: 7ms

memory: 5228kb

input:

output:

result:

ok single line: '355'

Test #67:

score: 0

Accepted

time: 11ms

memory: 5180kb

input:

output:

result:

ok single line: '3411'

Test #68:

score: 0

Accepted

time: 9ms

memory: 5128kb

input:

output:

result:

ok single line: '296'

Test #69:

score: 0

Accepted

time: 7ms

memory: 5068kb

input:

output:

result:

ok single line: '438'

Test #70:

score: 0

Accepted

time: 7ms

memory: 5144kb

input:

output:

result:

ok single line: '3397'

Test #71:

score: 0

Accepted

time: 3ms

memory: 5016kb

input:

output:

result:

ok single line: '100'

Test #72:

score: 0

Accepted

time: 10ms

memory: 5020kb

input:

output:

result:

ok single line: '495'

Test #73:

score: 0

Accepted

time: 11ms

memory: 5060kb

input:

output:

result:

ok single line: '4870'

Test #74:

score: 0

Accepted

time: 12ms

memory: 5072kb

input:

output:

result:

ok single line: '3799'

Test #75:

score: 0

Accepted

time: 27ms

memory: 5048kb

input:

output:

result:

ok single line: '615'

Test #76:

score: 0

Accepted

time: 52ms

memory: 4960kb

input:

output:

result:

ok single line: '3021'

Test #77:

score: 0

Accepted

time: 27ms

memory: 5016kb

input:

output:

result:

ok single line: '100'

Test #78:

score: 0

Accepted

time: 40ms

memory: 5124kb

input:

output:

result:

ok single line: '1004'

Test #79:

score: 0

Accepted

time: 70ms

memory: 5088kb

input:

output:

result:

ok single line: '3273'

Test #80:

score: 0

Accepted

time: 32ms

memory: 4952kb

input:

output:

result:

ok single line: '100'

Test #81:

score: 0

Accepted

time: 44ms

memory: 5072kb

input:

output:

result:

ok single line: '697'

Test #82:

score: 0

Accepted

time: 68ms

memory: 5128kb

input:

output:

result:

ok single line: '3120'

Test #83:

score: 0

Accepted

time: 46ms

memory: 5076kb

input:

output:

result:

ok single line: '288'

Test #84:

score: 0

Accepted

time: 42ms

memory: 5100kb

input:

output:

result:

ok single line: '774'

Test #85:

score: 0

Accepted

time: 80ms

memory: 5168kb

input:

output:

result:

ok single line: '5020'

Test #86:

score: 0

Accepted

time: 60ms

memory: 5236kb

input:

output:

result:

ok single line: '296'

Test #87:

score: 0

Accepted

time: 3ms

memory: 5084kb

input:

output:

result:

ok single line: '108'

Test #88:

score: 0

Accepted

time: 3ms

memory: 5128kb

input:

output:

result:

ok single line: '988'

Test #89:

score: 0

Accepted

time: 3ms

memory: 5156kb

input:

output:

result:

ok single line: '100'

Test #90:

score: 0

Accepted

time: 3ms

memory: 5024kb

input:

output:

result:

ok single line: '198'

Test #91:

score: 0

Accepted

time: 3ms

memory: 5020kb

input:

output:

result:

ok single line: '975'

Test #92:

score: 0

Accepted

time: 3ms

memory: 5156kb

input:

output:

result:

ok single line: '100'

Test #93:

score: 0

Accepted

time: 1ms

memory: 5136kb

input:

output:

result:

ok single line: '232'

Test #94:

score: 0

Accepted

time: 0ms

memory: 5076kb

input:

output:

result:

ok single line: '973'

Test #95:

score: 0

Accepted

time: 2ms

memory: 5188kb

input:

output:

result:

ok single line: '987'

Test #96:

score: 0

Accepted

time: 3ms

memory: 5116kb

input:

output:

result:

ok single line: '140'

Test #97:

score: 0

Accepted

time: 2ms

memory: 5168kb

input:

output:

result:

ok single line: '991'

Test #98:

score: 0

Accepted

time: 3ms

memory: 5108kb

input:

output:

result:

ok single line: '500'

Test #99:

score: 0

Accepted

time: 11ms

memory: 5140kb

input:

output:

result:

ok single line: '669'

Test #100:

score: 0

Accepted

time: 17ms

memory: 5136kb

input:

output:

result:

ok single line: '7604'

Test #101:

score: 0

Accepted

time: 15ms

memory: 5260kb

input:

output:

result:

ok single line: '300'

Test #102:

score: 0

Accepted

time: 15ms

memory: 5136kb

input:

output:

result:

ok single line: '738'

Test #103:

score: 0

Accepted

time: 28ms

memory: 5056kb

input:

output:

result:

ok single line: '7805'

Test #104:

score: 0

Accepted

time: 10ms

memory: 5072kb

input:

output:

result:

ok single line: '100'

Test #105:

score: 0

Accepted

time: 15ms

memory: 5136kb

input:

output:

result:

ok single line: '964'

Test #106:

score: 0

Accepted

time: 27ms

memory: 5164kb

input:

output:

result:

ok single line: '7980'

Test #107:

score: 0

Accepted

time: 11ms

memory: 5088kb

input:

output:

result:

ok single line: '100'

Test #108:

score: 0

Accepted

time: 15ms

memory: 4992kb

input:

output:

result:

ok single line: '885'

Test #109:

score: 0

Accepted

time: 26ms

memory: 5064kb

input:

output:

result:

ok single line: '8710'

Test #110:

score: 0

Accepted

time: 23ms

memory: 5052kb

input:

output:

result:

ok single line: '786'

Test #111:

score: 0

Accepted

time: 98ms

memory: 5120kb

input:

output:

result:

ok single line: '1728'

Test #112:

score: 0

Accepted

time: 157ms

memory: 5168kb

input:

output:

result:

ok single line: '8720'

Test #113:

score: 0

Accepted

time: 108ms

memory: 5156kb

input:

output:

result:

ok single line: '299'