QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#354008 | #8137. 'Ello, and What Are You After, Then? | SolitaryDream# | TL | 2ms | 3932kb | C++17 | 3.8kb | 2024-03-14 20:29:48 | 2024-03-14 20:29:49 |
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];
struct DS {
multiset<double> in, out;
double sum;
int c;
void init(int _c) {
c = _c;
}
void clear() {
in.clear(), out.clear();
sum = 0;
c = 0;
}
void del(double w) {
if(in.find(w) != in.end())
in.erase(w), sum -= w;
if(in.size() < c) {
if(out.size()) {
auto it = out.end();
it--;
in.insert(*it);
sum += *it;
out.erase(it);
}
}
}
void ins(double x) {
in.insert(x);
sum += x;
if(in.size() > c && *in.begin() < 0) {
sum -= *in.begin();
in.erase(in.begin());
}
}
}W;
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);
double ans = -1e9;
// for (int s = 0; s < (1 << m[o]); ++s) if (__builtin_popcount(s) >= cnt) {
// double cur = 0;
// for (int i = 0; i < m[o]; ++i) if (s >> i & 1) cur += max(A[i], B[i]);
// ans = max(ans, cur);
// }
// vector<int> ord(m[o]);
// iota(ord.begin(), ord.end(), 0);
// sort(ord.begin(), ord.end(), [&](const int &x, const int &y) {return A[x] - B[x] < A[y] - B[y];});
// W.clear();
// W.init(cnt);
// for(int i = 0; i < m[o]; i += 1)
// W.ins(B[i]);
// ans = max(ans, W.sum);
// for(int i = 0; i < m[o]; i += 1) {
// W.del(B[i]);
// W.
// }
sort(mx.begin(), mx.end(), greater<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 = -1e10, minR = 0;
for (int i = 1; i <= n; ++i) {
// npc i
double L = -1e10, R = 0;
for (int r = 0; r < 100; ++r) {
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 = -1e10, R = p;
for (int r = 0; r < 50; ++r) {
double mid = (L + R) * 0.5;
if (Calc(i, E, mid) >= 0) L = mid;
else R = mid;
}
double pl = L;
L = p, R = 0;
for (int r = 0; r < 50; ++r) {
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;
for (int i = 0; i < 40; ++i) {
double mid = (L + R) * 0.5;
if (Check(mid)) L = mid;
else R = mid;
}
cout << fixed << setprecision(15);
cout << L << endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3792kb
input:
0 1 6 2 1 1 1 1 2 1 10 1 1 10 10
output:
6.999997549428372
result:
ok found '6.9999975', expected '7.0000000', error '0.0000004'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3932kb
input:
2 1 2 1 4 10 2 1 10 1 1 1 10 1 1 1 10
output:
5.909090932618710
result:
ok found '5.9090909', expected '5.9090909', error '0.0000000'
Test #3:
score: -100
Time Limit Exceeded
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...