QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#354033#8137. 'Ello, and What Are You After, Then?SolitaryDreamWA 988ms4756kbC++172.5kb2024-03-14 20:43:312024-03-14 20:43:31

Judging History

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

  • [2024-03-14 20:43:31]
  • 评测
  • 测评结果:WA
  • 用时:988ms
  • 内存:4756kb
  • [2024-03-14 20:43:31]
  • 提交

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;
}

詳細信息

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'