QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#817751 | #1880. Nikanor Loves Games | The_8th_Horcrux# | WA | 0ms | 4112kb | C++23 | 2.9kb | 2024-12-17 11:31:28 | 2024-12-17 11:31:30 |
Judging History
answer
// Author : hejinming2012
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define dbg(x) cout << #x " = " << (x) << endl
#define quickio ios::sync_with_stdio(false);
#define quickin cin.tie(0);
#define quickout cout.tie(0);
using namespace std;
inline int read() {
int now = 0, nev = 1; char c = getchar();
while(c < '0' || c > '9') { if(c == '-') nev = -1; c = getchar(); }
while(c >= '0' && c <= '9') { now = (now << 1) + (now << 3) + (c & 15); c = getchar(); }
return now * nev;
}
void write(int x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
struct lin {
long long m, b;
};
bool is_bad(const lin& l1, const lin& l2, const lin& l3) {
return (__int128)(l2.b - l1.b) * (l1.m - l3.m) >= (__int128)(l3.b - l1.b) * (l1.m - l2.m);
}
signed main() {
quickio
quickin
quickout
int n = read();
struct frd { int a, b; long long x; };
vector<frd> f(n);
vector<int> all_k;
for(int i = 0; i < n; i++) {
f[i].a = read(); f[i].b = read(); f[i].x = read();
all_k.push_back(f[i].a); all_k.push_back(f[i].b);
}
sort(all_k.begin(), all_k.end());
all_k.erase(unique(all_k.begin(), all_k.end()), all_k.end());
int m = all_k.size();
vector<long long> sum_x(m, 0);
for(int i = 0; i < n; i++) {
int idx_a = lower_bound(all_k.begin(), all_k.end(), f[i].a) - all_k.begin();
int idx_b = lower_bound(all_k.begin(), all_k.end(), f[i].b) - all_k.begin();
sum_x[idx_a] += f[i].x;
sum_x[idx_b] += f[i].x;
}
vector<long long> F2(m, 0);
F2[0] = sum_x[0];
for(int i = 1; i < m; i++) F2[i] = F2[i-1] + sum_x[i];
long long sum_x_sum = 0;
for(int i = 0; i < n; i++) sum_x_sum += f[i].x;
deque<lin> hull;
auto add_line = [&](lin new_line) {
while(hull.size() >= 2 && is_bad(hull[hull.size()-2], hull[hull.size()-1], new_line)) {
hull.pop_back();
}
hull.push_back(new_line);
};
auto query = [&](long long x) -> long long {
while(hull.size() >= 2) {
long long y1 = hull[0].m * x + hull[0].b;
long long y2 = hull[1].m * x + hull[1].b;
if(y1 >= y2) break;
hull.pop_front();
}
if(hull.empty()) return LLONG_MIN;
return hull[0].m * x + hull[0].b;
};
long long max_value = LLONG_MIN;
for(int i = 0; i < m; i++) {
long long k = all_k[i];
lin new_line;
new_line.m = -2 * k;
new_line.b = F2[i];
add_line(new_line);
long long current_max = query(k);
long long current_value = F2[i] + current_max;
if(current_value > max_value) {
max_value = current_value;
}
}
double expected_profit = ((double)(max_value - 2LL * sum_x_sum)) / 2.0;
printf("%.10f", expected_profit);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3756kb
input:
2 1 4 15 3 5 10
output:
2.5000000000
result:
ok found '2.5000000', expected '2.5000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
1 2 2 8
output:
4.0000000000
result:
ok found '4.0000000', expected '4.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
3 94 68 49 51 2 63 26 85 20
output:
-73.0000000000
result:
ok found '-73.0000000', expected '-73.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 4104kb
input:
2 14 68 12 28 2 46
output:
-16.0000000000
result:
ok found '-16.0000000', expected '-16.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 4112kb
input:
5 6 6 8 6 1 11 6 1 13 6 1 5 5 1 2
output:
9.5000000000
result:
ok found '9.5000000', expected '9.5000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
5 5 4 2 4 1 10 3 1 3 2 1 3 5 1 5
output:
5.5000000000
result:
ok found '5.5000000', expected '5.5000000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4036kb
input:
5 1 5 2 4 2 7 2 2 2 2 5 14 1 4 2
output:
4.5000000000
result:
ok found '4.5000000', expected '4.5000000', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 4040kb
input:
5 4 1 9 1 5 13 3 6 10 6 5 8 3 5 5
output:
9.0000000000
result:
ok found '9.0000000', expected '9.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
5 3 7 9 5 7 12 4 6 13 3 6 6 2 1 2
output:
-6.0000000000
result:
ok found '-6.0000000', expected '-6.0000000', error '-0.0000000'
Test #10:
score: -100
Wrong Answer
time: 0ms
memory: 3980kb
input:
10 8 10 26 11 2 28 13 4 13 11 1 26 6 15 23 12 8 7 9 8 11 11 10 17 8 11 18 3 10 27
output:
-13.0000000000
result:
wrong answer 1st numbers differ - expected: '32.0000000', found: '-13.0000000', error = '1.4062500'