QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#817751#1880. Nikanor Loves GamesThe_8th_Horcrux#WA 0ms4112kbC++232.9kb2024-12-17 11:31:282024-12-17 11:31:30

Judging History

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

  • [2024-12-17 11:31:30]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4112kb
  • [2024-12-17 11:31:28]
  • 提交

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'