QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#354008#8137. 'Ello, and What Are You After, Then?SolitaryDream#TL 2ms3932kbC++173.8kb2024-03-14 20:29:482024-03-14 20:29:49

Judging History

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

  • [2024-03-14 20:29:49]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:3932kb
  • [2024-03-14 20:29:48]
  • 提交

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...

output:


result: