QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#354011 | #8137. 'Ello, and What Are You After, Then? | SolitaryDream# | WA | 3ms | 3840kb | C++17 | 3.8kb | 2024-03-14 20:30:18 | 2024-03-14 20:30:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10, EF = 75;
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 < EF; ++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 < EF; ++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 < EF; ++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 < EF; ++i) {
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: 3ms
memory: 3840kb
input:
0 1 6 2 1 1 1 1 2 1 10 1 1 10 10
output:
6.999999999999913
result:
ok found '7.0000000', expected '7.0000000', error '0.0000000'
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3836kb
input:
2 1 2 1 4 10 2 1 10 1 1 1 10 1 1 1 10
output:
5.910698488298289
result:
wrong answer 1st numbers differ - expected: '5.9090909', found: '5.9106985', error = '0.0002721'