QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#215053 | #6547. Banshee | ucup-team1766# | TL | 1ms | 3716kb | C++23 | 1.4kb | 2023-10-15 02:43:14 | 2023-10-15 02:43:14 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct building {
long long l;
int t;
};
void run() {
int n, m; cin >> n >> m;
vector<building> b(n);
long long sum = 0;
for (int i = 0; i < n; i++) {
long long x;
int h, s;
cin >> b[i].l >> x >> h >> s;
b[i].l = max(0ll, b[i].l - 6);
b[i].t = (h+s+23)/24;
sum += b[i].t;
}
auto can = [&](double limit) {
vector<building> b2(b);
long long pos = 0;
int banshees = m;
for (int i = 0; i < n; i++) {
limit -= (b2[i].l - pos) / 5.25;
pos = b2[i].l;
long long damage = limit/.89;
int total = b2[i].t;
int sac = total/damage;
banshees -= sac;
total -= sac*damage;
if (total > 0) {
double limit2 = limit;
long long pos2 = pos;
limit2 -= total*.89;
banshees -= 1;
while (limit2 >= .89) {
i++;
if (i == n) break;
limit2 -= (b2[i].l - pos2) / 5.25;
pos2 = b2[i].l;
damage = min((int)(limit2/.89), b2[i].t);
b2[i].t -= damage;
limit2 -= damage*.89;
}
i--;
}
if (banshees < 0) {
return false;
}
}
return true;
};
double low = b[n-1].l/5.25 + sum*.89/m;
double high = sum*.89 + b[n-1].l/5.25 + 2;
while (high - low > 1e-5) {
double mid = (low+high)/2;
//cout << low << ' ' << high << endl;
if (can(mid)) {
high = mid;
} else {
low = mid + 1e-5;
}
}
cout << fixed << setprecision(13) << low << '\n';
}
int main() {
int t; cin >> t;
while (t--) run();
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3716kb
input:
2 2 1 1 2 1 100 100 500 736 0 3 2 0 1 12 0 1 2 6 6 2 3 3 10
output:
49.9447619047619 1.7800012548828
result:
ok 2 numbers
Test #2:
score: -100
Time Limit Exceeded
input:
1 1 1 999999999999 1000000000000 1000000 1000000