QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#421897 | #6458. Programming Team | nitrousoxide# | TL | 1ms | 4004kb | C++14 | 1.4kb | 2024-05-26 09:36:13 | 2024-05-26 09:36:13 |
Judging History
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...