QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#369358#1880. Nikanor Loves GamesNeltTL 1ms4096kbC++202.3kb2024-03-28 03:51:442024-03-28 03:51:45

Judging History

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

  • [2024-03-28 03:51:45]
  • 评测
  • 测评结果：TL
  • 用时：1ms
  • 内存：4096kb
查看
  • [2024-03-28 03:51:44]
  • 提交

answer

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define ll long long
#define endl "\n"
using namespace std;
ll intersection(long double k, long double b, long double k1, long double b1)
{
    return k == k1 ? -1e18 : (b1 - b) / (k - k1);
}
void solve()
{
    ll n;
    cin >> n;
    pair<ll, ll> a[n], b[n];
    for (ll i = 0; i < n; i++)
        cin >> a[i].first >> b[i].first >> a[i].second, b[i].second = a[i].second;
    sort(a, a + n);
    sort(b, b + n);
    pair<ll, ll> c[n + n + 1];
    c[0] = make_pair(1, 0);
    merge(a, a + n, b, b + n, c + 1);
    vector<array<ll, 3>> v;
    ll sum = 0, ptr = 0;
    long double k[2 * n + 1];
    for (ll i = 0; i <= 2 * n; i++)
    {
        while (ptr <= 2 * n and c[ptr].first <= c[i].first)
            sum += c[ptr++].second;
        k[i] = sum / 2.0;
        array<ll, 3> cur = {(ll)-1e9, (ll)1e9, i};
        while (!v.empty() and c[ptr].first * v.back()[0] + k[i] > c[v.back()[2]].first * v.back()[0] + k[v.back()[2]])
            cur[0] = v.back()[0], v.pop_back();
        if (v.empty())
            v.push_back({(ll)-1e9, (ll)1e9, i});
        else
        {
            ll point = intersection(c[i].first, k[i], c[v.back()[2]].first, k[v.back()[2]]);
            if (point != -1e18)
                cur[0] = point + 1, v.back()[1] = point, v.push_back(cur);
        }
    }
    long double ans = 0;
    sum = 0;
    ptr = 0;
    for (ll i = 0; i <= 2 * n; i++)
    {
        while (ptr <= 2 * n and c[ptr].first <= c[i].first)
            sum += c[ptr++].second;
        ll pos = upper_bound(v.begin(), v.end(), array<ll, 3>{-c[i].first, (ll)1e9, (ll)1e9}) - v.begin();
        // cout << sum << " ";
        // for (ll j = max(0ll, pos - 1); j <= min((ll)v.size() - 1, pos); j++)
        for (ll j = 0; j <= 2 * n; j++)
            ans = max(ans, k[j] - c[j].first * c[i].first + sum / 2.0);
    }
    for (ll i = 0; i < n; i++)
        ans -= a[i].second;
    cout << setprecision(10) << fixed << ans << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // precomp();
    // cin >> t;
    for (ll i = 1; i <= t; i++)
        solve();
    cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3916kb

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: 1ms
memory: 4088kb

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: 1ms
memory: 3856kb

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: 3804kb

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: 3816kb

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: 3972kb

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: 1ms
memory: 4096kb

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: 3916kb

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: 1ms
memory: 3800kb

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: 0
Accepted
time: 0ms
memory: 3816kb

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:

32.0000000000

result:

ok found '32.0000000', expected '32.0000000', error '0.0000000'

Test #11:

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

input:

10
6 5 10
10 15 21
7 2 30
14 6 12
1 11 6
1 13 19
8 13 29
9 4 14
1 4 29
4 12 17

output:

12.0000000000

result:

ok found '12.0000000', expected '12.0000000', error '0.0000000'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3948kb

input:

10
5 15 15
3 14 20
11 14 26
15 12 22
5 15 11
12 10 10
1 12 18
7 7 14
3 5 10
12 9 23

output:

-6.0000000000

result:

ok found '-6.0000000', expected '-6.0000000', error '-0.0000000'

Test #13:

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

input:

10
3 9 29
9 5 27
14 13 21
3 15 15
14 11 24
9 14 22
9 3 20
12 15 27
5 13 21
13 11 14

output:

-5.0000000000

result:

ok found '-5.0000000', expected '-5.0000000', error '-0.0000000'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3916kb

input:

10
3 13 11
3 5 20
9 10 1
5 5 25
10 1 29
6 10 26
1 15 1
10 10 18
6 6 2
14 6 20

output:

21.0000000000

result:

ok found '21.0000000', expected '21.0000000', error '0.0000000'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

100
68 91 90
56 38 71
69 57 87
80 62 21
31 80 25
36 48 40
71 66 49
15 57 78
96 69 43
25 73 57
86 13 5
23 98 18
83 94 9
8 22 43
46 3 50
81 11 26
14 35 39
49 68 73
41 11 25
35 47 48
5 96 15
15 56 60
42 1 40
11 4 25
57 72 9
43 3 90
16 45 36
83 50 17
55 40 39
72 37 6
70 84 24
12 36 95
43 15 13
82 28 68
...

output:

35.5000000000

result:

ok found '35.5000000', expected '35.5000000', error '0.0000000'

Test #16:

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

input:

100
92 35 39
34 92 36
45 45 46
66 5 64
22 21 48
53 70 91
93 19 98
97 67 54
57 77 64
90 81 23
12 83 92
59 3 26
13 65 47
19 23 58
27 58 38
60 18 70
32 94 53
100 66 97
33 53 16
56 2 64
8 9 55
93 92 22
27 25 39
45 49 24
76 80 89
73 55 77
69 53 90
39 77 40
86 12 11
23 87 25
8 96 31
73 45 98
52 62 55
98 9...

output:

-100.0000000000

result:

ok found '-100.0000000', expected '-100.0000000', error '-0.0000000'

Test #17:

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

input:

100
20 84 93
15 45 13
28 33 2
49 41 12
12 50 59
62 89 49
11 60 42
74 84 33
14 94 85
51 2 89
26 66 87
92 12 26
47 32 84
34 16 80
20 16 27
48 34 14
54 61 66
52 47 21
41 87 3
81 45 68
24 18 94
71 23 87
12 49 34
79 6 6
91 92 56
3 15 64
22 69 41
91 3 60
21 76 79
65 41 48
46 9 35
34 54 92
68 10 1
22 82 17...

output:

25.5000000000

result:

ok found '25.5000000', expected '25.5000000', error '0.0000000'

Test #18:

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

input:

100
44 28 47
89 7 89
7 21 57
27 92 56
14 96 86
79 11 7
29 4 95
56 93 16
71 2 6
100 14 59
53 32 82
24 20 35
73 7 22
44 9 91
5 70 24
31 41 50
72 19 80
100 44 46
33 26 94
2 4 72
27 35 29
49 54 44
92 73 33
13 55 92
6 3 31
37 76 47
75 77 87
44 33 80
63 48 51
12 90 66
83 17 46
99 59 78
76 61 35
39 52 91
9...

output:

-57.0000000000

result:

ok found '-57.0000000', expected '-57.0000000', error '-0.0000000'

Test #19:

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

input:

100
68 73 96
63 60 58
86 13 29
13 32 95
4 25 97
96 30 61
55 57 43
34 98 95
32 14 27
65 26 38
79 10 69
56 33 35
98 82 59
55 9 5
82 25 12
19 53 94
90 82 6
48 29 70
29 60 76
23 59 89
38 44 64
31 81 10
77 96 24
51 99 79
25 19 11
68 32 34
28 89 38
100 64 4
94 16 19
58 40 89
17 34 57
64 69 80
92 12 81
63 ...

output:

-81.5000000000

result:

ok found '-81.5000000', expected '-81.5000000', error '-0.0000000'

Test #20:

score: -100
Time Limit Exceeded

input:

200000
14 11 10
2 6 10
18 13 7
8 5 11
13 5 14
16 14 2
4 5 17
4 20 7
7 3 9
9 8 11
15 1 20
19 13 3
19 17 15
9 16 20
5 5 15
2 1 6
11 14 13
8 13 7
2 3 10
7 18 9
1 4 12
17 3 7
14 4 17
12 14 11
18 11 6
11 7 15
10 4 13
13 2 14
2 1 18
7 3 18
12 16 19
17 13 7
7 17 1
20 9 2
2 1 2
6 13 11
7 11 9
20 16 3
9 4 4
...

output:

result:
English 繁體中文 简体中文

Server Time: 2025-02-01 20:51:14 | OpenSource Project