QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#421897#6458. Programming Teamnitrousoxide#TL 1ms4004kbC++141.4kb2024-05-26 09:36:132024-05-26 09:36:13

Judging History

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

  • [2024-05-26 09:36:13]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4004kb
  • [2024-05-26 09:36:13]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2600;

typedef long long ll;

vector<int> g[maxn];
ll s[maxn], p[maxn];
int  r[maxn];
int siz[maxn];
ll dp[maxn][maxn];
ll mid;
int k;

void dfs(int u) {
    siz[u] = 1;
    dp[u][1] = p[u] * 10000 - mid * s[u];
    for (auto v : g[u]) {
        if (v != r[u]) {
            dfs(v);
            for (int i = min(k+1, siz[u] + siz[v]); i >= 2; i--) {
                for (int j = 1; j <= min(siz[v], i); j++) {
                    dp[u][i] = max(dp[u][i], dp[u][i-j] + dp[v][j]);
                }
            }
            siz[u] += siz[v];
        }
    }
}

int main() {
    int n;
    cin >> k >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i] >> p[i] >> r[i];
        g[r[i]].push_back(i);
        g[i].push_back(r[i]);
    }

    ll lower = 0;
    ll upper = 100050000;
    ll ans = 0;
    while (lower <= upper) {
        mid = (lower + upper) / 2;  
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k+1; j++) {
                dp[i][j] = -1ll << 50;
            }
        }
        dfs(0);
        if (dp[0][k+1] < 0) {
            upper = mid - 1;
        } else {
            lower = mid + 1;
            ans = mid;
        }
    }
    cout << fixed << setprecision(3);
    cout << double(ans / (double)10000 + 1e-5) << endl;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 4004kb

input:

1 2
1000 1 0
1 1000 1

output:

0.001

result:

ok single line: '0.001'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3996kb

input:

2 3
1 100 0
1 200 0
1 300 0

output:

250.000

result:

ok single line: '250.000'

Test #3:

score: -100
Time Limit Exceeded

input:

597 1985
9708 32 0
9970 599 1
9876 366 2
9623 44 3
9167 1395 4
9997 431 5
7825 440 6
9999 148 7
9778 2086 8
9655 2504 9
9619 34 10
8550 268 11
9978 108 12
9998 102 13
9861 7 14
9242 240 15
9044 43 16
9900 221 17
9393 692 18
9996 3470 19
8817 3617 20
9086 103 21
9563 71 22
9962 6 23
9872 5000 23
9928...

output:


result: