QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#354037#8137. 'Ello, and What Are You After, Then?SolitaryDreamWA 883ms4388kbC++172.4kb2024-03-14 20:45:092024-03-14 20:45:09

Judging History

This is the latest submission verdict.

  • [2024-03-14 20:45:09]
  • Judged
  • Verdict: WA
  • Time: 883ms
  • Memory: 4388kb
  • [2024-03-14 20:45:09]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
const double eps = 1e-8;
int B, C, S;
int n, m[N];
struct Task {
    int f, t;
    double e;
};
vector<Task> npc[N];
vector<double> mx;

inline double Calc(int o, double E, double k) {
    mx.resize(m[o]);
    for (int i = 0; i < m[o]; ++i) {
        auto [f, t, e] = npc[o][i];
        mx[i] = (max(f * (e - E) * t - C * k * f, S * k * f));
    }
    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) > eps) {
            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) > eps) {
            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) > eps) {
            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) > eps) {
        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: 1ms
memory: 3968kb

input:

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

output:

6.999999968684278

result:

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

Test #2:

score: 0
Accepted
time: 1ms
memory: 3888kb

input:

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

output:

5.909090905333869

result:

ok found '5.9090909', expected '5.9090909', error '0.0000000'

Test #3:

score: 0
Accepted
time: 563ms
memory: 4384kb

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

result:

ok found '1453.3645753', expected '1453.3645790', error '0.0000000'

Test #4:

score: 0
Accepted
time: 338ms
memory: 4128kb

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: 883ms
memory: 4100kb

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

result:

ok found '5092.9934159', expected '5092.9934521', error '0.0000000'

Test #6:

score: 0
Accepted
time: 257ms
memory: 4008kb

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

result:

ok found '5067.1698898', expected '5067.1699032', error '0.0000000'

Test #7:

score: -100
Wrong Answer
time: 115ms
memory: 4388kb

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

result:

wrong answer 1st numbers differ - expected: '5560.1314972', found: '5578.2346427', error = '0.0032559'