QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#354013#8137. 'Ello, and What Are You After, Then?SolitaryDream#WA 4ms4000kbC++173.8kb2024-03-14 20:30:352024-03-14 20:30:36

Judging History

你现在查看的是最新测评结果

  • [2024-03-14 20:30:36]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:4000kb
  • [2024-03-14 20:30:35]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10, EF = 80;
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: 4ms
memory: 3996kb

input:

0 1 6
2
1
1 1 1
2
1 10 1
1 10 10

output:

6.999999999999998

result:

ok found '7.0000000', expected '7.0000000', error '0.0000000'

Test #2:

score: -100
Wrong Answer
time: 3ms
memory: 4000kb

input:

2 1 2
1
4
10 2 1
10 1 1
1 10 1
1 1 10

output:

5.909217600260840

result:

wrong answer 1st numbers differ - expected: '5.9090909', found: '5.9092176', error = '0.0000214'