QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#354033 | #8137. 'Ello, and What Are You After, Then? | SolitaryDream | WA | 988ms | 4756kb | C++17 | 2.5kb | 2024-03-14 20:43:31 | 2024-03-14 20:43:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int B, C, S;
int n, m[N];
struct Task {
int f, t;
double e;
};
vector<Task> npc[N];
inline double Calc(int o, double E, double k) {
vector<double> A(m[o]), B(m[o]);
vector<double> mx;
for (int i = 0; i < m[o]; ++i) {
auto [f, t, e] = npc[o][i];
A[i] = f * (e - E) * t - C * k * f;
B[i] = S * k * f;
mx.push_back(max(A[i], B[i]));
}
int cnt = max(m[o] - ::B, 0);
// sort(mx.begin(), mx.end(), greater<double>());
nth_element(mx.begin(), mx.begin() + cnt, mx.end(), greater<double>());
double ans = 0;
for(int i = 0; i < cnt; i += 1)
ans += mx[i];
for(int i = cnt; i < m[o]; i += 1)
if(mx[i] > 0)
ans += mx[i];
return ans;
}
inline bool Check(double E) {
double maxL = -1e3, minR = 0;
for (int i = 1; i <= n; ++i) {
// npc i
double L = -1e3, R = 0;
while((R - L) / max(1., R) > 1e-6) {
double m1 = L + (R - L) / 3;
double m2 = R - (R - L) / 3;
if (Calc(i, E, m1) > Calc(i, E, m2)) L = m1;
else R = m2;
}
double p = L;
// cout << L << ' ' << R << ' ' << Calc(i, E, p) << endl;
// exit(0);
if (Calc(i, E, p) > 0) return 1;
L = -1e3, R = p;
while((R - L) / max(1., -L) > 1e-6) {
double mid = (L + R) * 0.5;
if (Calc(i, E, mid) >= 0) L = mid;
else R = mid;
}
double pl = L;
L = p, R = 0;
while ((R - L) / max(1., -L) > 1e-6) {
double mid = (L + R) * 0.5;
if (Calc(i, E, mid) >= 0) R = mid;
else L = mid;
}
double pr = L;
if (pr < maxL || pl > minR) return 1;
maxL = max(maxL, pl);
minR = min(minR, pr);
}
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> B >> C >> S;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> m[i];
npc[i].resize(m[i]);
for (auto &[f, t, e] : npc[i]) cin >> f >> t >> e;
sort(npc[i].begin(), npc[i].end(), [](Task u, Task v) { return u.f < v.f; });
}
double L = 0, R = 1e4;
while((R - L) / max(1., R) > 1e-7) {
double mid = (L + R) * 0.5;
if (Check(mid)) L = mid;
else R = mid;
}
cout << fixed << setprecision(15);
cout << L << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3904kb
input:
0 1 6 2 1 1 1 1 2 1 10 1 1 10 10
output:
7.000000332482159
result:
ok found '7.0000003', expected '7.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3900kb
input:
2 1 2 1 4 10 2 1 10 1 1 1 10 1 1 1 10
output:
5.909092724323273
result:
ok found '5.9090927', expected '5.9090909', error '0.0000003'
Test #3:
score: 0
Accepted
time: 954ms
memory: 4324kb
input:
14 1000 1000 1000 30 113 80 1188 92 145 1074 130 56 1296 139 102 1142 60 76 1317 128 126 1208 73 120 1155 91 89 1197 115 64 979 80 118 592 110 97 556 83 105 578 94 51 848 98 134 757 107 138 1038 105 143 892 92 72 893 88 103 961 87 148 879 105 84 823 85 134 607 100 82 1084 199 58 801 138 85 743 214 1...
output:
1453.364565968513489
result:
ok found '1453.3645660', expected '1453.3645790', error '0.0000000'
Test #4:
score: 0
Accepted
time: 563ms
memory: 4748kb
input:
8720 713 168 1 30000 1 186 5272 2 53 5132 2 124 5529 2 186 5052 2 82 5342 2 178 5027 1 74 5271 2 154 5506 1 185 5225 2 60 5068 2 85 5179 1 193 5231 1 94 5469 2 168 5317 2 142 5153 2 44 5083 2 71 5318 2 53 5325 1 68 5051 2 53 5424 2 150 5125 2 122 5371 2 126 5171 2 39 5315 2 57 5193 1 130 5203 2 179 ...
output:
5276.127159595489502
result:
ok found '5276.1271596', expected '5276.1271835', error '0.0000000'
Test #5:
score: 0
Accepted
time: 988ms
memory: 4756kb
input:
19121 34 288 1 30000 8 213 5200 10 169 5148 6 228 5033 11 83 5151 10 98 5200 10 228 5124 7 111 5091 9 218 5114 9 115 5198 10 142 5027 10 221 5105 7 201 5191 10 153 5002 7 130 5186 11 131 5116 10 115 5030 9 124 5053 9 225 5039 10 100 5109 9 170 5202 9 220 5125 11 187 5056 12 115 5062 9 218 5103 6 139...
output:
5092.993378639221191
result:
ok found '5092.9933786', expected '5092.9934521', error '0.0000000'
Test #6:
score: 0
Accepted
time: 412ms
memory: 4220kb
input:
6753 181 9 3 10000 13 948 5040 22 140 5020 10 265 5037 24 1021 5027 12 841 5081 15 202 5034 15 606 5052 11 140 5040 12 1071 5025 9 1045 5022 23 504 5026 19 1213 5085 24 839 5075 12 549 5080 23 643 5025 15 434 5070 25 578 5007 10 132 5030 16 335 5034 21 329 5085 8 239 5084 22 447 5082 26 168 5004 22 ...
output:
5067.169666290283203
result:
ok found '5067.1696663', expected '5067.1699032', error '0.0000000'
Test #7:
score: -100
Wrong Answer
time: 479ms
memory: 4380kb
input:
0 3 4 1000 30 36 868 5560 34 896 5226 34 867 5493 32 818 5036 34 1012 5202 37 1136 5475 36 1110 5146 30 1128 5199 33 912 5218 33 903 5398 36 786 5018 37 744 5551 30 997 5120 35 826 5484 32 1133 5300 35 783 5294 32 840 5119 36 958 5186 36 798 5115 37 981 5482 37 792 5390 32 888 5120 31 794 5065 35 99...
output:
5578.234493732452393
result:
wrong answer 1st numbers differ - expected: '5560.1314972', found: '5578.2344937', error = '0.0032559'