QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #29500 | #1880. Nikanor Loves Games | cdw | WA | 3ms | 3764kb | C++20 | 1.1kb | 2022-04-18 22:24:31 | 2022-04-28 15:11:58 |
Judging History
answer
#include<bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef __int128 LLL;
typedef pair<int, LL> pil;
template<typename T>
bool chmax(T &a, const T &b){if(a < b) return a = b, 1; return 0;}
const int N = 400003;
int n, m; LL sum, ans;
pil a[N], b[N];
int main(){
ios::sync_with_stdio(false);
cin >> n; a[0] = MP(1, 0);
for(int i = 0, b, c, x;i < n;++ i){
cin >> b >> c >> x; sum += x;
a[i<<1|1] = MP(b, x); a[i+1<<1] = MP(c, x);
}
sort(a, a + (n<<1|1));
for(int i = 1;i <= (n<<1);++ i) a[i].se += a[i-1].se;
for(int i = 0;i <= (n<<1);++ i){
while(m > 1 && ((LLL)a[i].se-b[m-1].se)*(a[i].fi-b[m-2].fi) > ((LLL)a[i].se-b[m-2].se)*(a[i].fi-b[m-1].fi)) -- m;
b[m++] = a[i];
}
for(int i = 0, j = m-1;i < m;++ i){
while(j && b[j].se - 2ll * b[j].fi * b[i].fi < b[j-1].se - 2ll * b[j-1].fi * b[i].fi) -- j;
chmax(ans, b[i].se + b[j].se - 2ll * b[i].fi * b[j].fi);
}
printf("%lld.%lld\n", (ans>>1)-sum, 5*(ans&1));
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3740kb
input:
2 1 4 15 3 5 10
output:
2.5
result:
ok found '2.5000000', expected '2.5000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3740kb
input:
1 2 2 8
output:
4.0
result:
ok found '4.0000000', expected '4.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 3ms
memory: 3712kb
input:
3 94 68 49 51 2 63 26 85 20
output:
-73.0
result:
ok found '-73.0000000', expected '-73.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 3ms
memory: 3720kb
input:
2 14 68 12 28 2 46
output:
-16.0
result:
ok found '-16.0000000', expected '-16.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
5 6 6 8 6 1 11 6 1 13 6 1 5 5 1 2
output:
9.5
result:
ok found '9.5000000', expected '9.5000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
5 5 4 2 4 1 10 3 1 3 2 1 3 5 1 5
output:
5.5
result:
ok found '5.5000000', expected '5.5000000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
5 1 5 2 4 2 7 2 2 2 2 5 14 1 4 2
output:
4.5
result:
ok found '4.5000000', expected '4.5000000', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
5 4 1 9 1 5 13 3 6 10 6 5 8 3 5 5
output:
9.0
result:
ok found '9.0000000', expected '9.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 3ms
memory: 3764kb
input:
5 3 7 9 5 7 12 4 6 13 3 6 6 2 1 2
output:
-6.0
result:
ok found '-6.0000000', expected '-6.0000000', error '-0.0000000'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3708kb
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.0
result:
ok found '32.0000000', expected '32.0000000', error '0.0000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3692kb
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.0
result:
ok found '12.0000000', expected '12.0000000', error '0.0000000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3640kb
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.0
result:
ok found '-6.0000000', expected '-6.0000000', error '-0.0000000'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3724kb
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.0
result:
ok found '-5.0000000', expected '-5.0000000', error '-0.0000000'
Test #14:
score: 0
Accepted
time: 3ms
memory: 3724kb
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.0
result:
ok found '21.0000000', expected '21.0000000', error '0.0000000'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3648kb
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.5
result:
ok found '35.5000000', expected '35.5000000', error '0.0000000'
Test #16:
score: 0
Accepted
time: 2ms
memory: 3744kb
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.0
result:
ok found '-100.0000000', expected '-100.0000000', error '-0.0000000'
Test #17:
score: 0
Accepted
time: 2ms
memory: 3744kb
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.5
result:
ok found '25.5000000', expected '25.5000000', error '0.0000000'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3720kb
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.0
result:
ok found '-57.0000000', expected '-57.0000000', error '-0.0000000'
Test #19:
score: -100
Wrong Answer
time: 2ms
memory: 3740kb
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:
-82.5
result:
wrong answer 1st numbers differ - expected: '-81.5000000', found: '-82.5000000', error = '0.0122699'