QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #330172 | #1880. Nikanor Loves Games | masterhuang | WA | 33ms | 23424kb | C++20 | 1.0kb | 2024-02-17 13:24:35 | 2024-02-17 13:24:35 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define LD long double
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=1e6+15;
int n,m,a[N],b[N],w[N],hd,tl,q[N];LL ans,s[N],mx=-1e18,f[N];
struct node{int x,w;bool operator<(node X){return x<X.x;}}c[N];
#define X(i) (c[i].x)
#define Y(x) (s[x])
inline LD sp(int a1,int a2){return (X(a1)==X(a2))?(Y(a2)>Y(a1)?1e18:-1e18):(LD)(Y(a2)-Y(a1))/(X(a2)-X(a1));}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;c[m=1]={1,0};
for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>w[i],w[i]<<=1,ans-=2ll*w[i],c[++m]={a[i],w[i]},c[++m]={b[i],w[i]};
sort(c+1,c+1+m);
for(int i=1;i<=m;i++) s[i]=s[i-1]+c[i].w;
for(int i=1;i<=m;i++) mx=max(mx,2*s[i]-4ll*c[i].x*c[i].x);hd=1;
for(int i=1;i<=m;i++)
{
while(hd<tl&&sp(q[tl-1],q[tl])<=4ll*c[i].x) tl--;
int t=q[tl];if(t) f[i]=s[i]+s[t]-4ll*c[i].x*c[t].x;
while(hd<tl&&sp(q[tl-1],q[tl])<=sp(q[tl],i)) tl--;q[++tl]=i;
}
return cout<<(ans+max(mx,*max_element(f+1,f+1+m)))/4.0,0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 14076kb
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: 0ms
memory: 14112kb
input:
1 2 2 8
output:
4
result:
ok found '4.0000000', expected '4.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 2ms
memory: 14120kb
input:
3 94 68 49 51 2 63 26 85 20
output:
-73
result:
ok found '-73.0000000', expected '-73.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 14124kb
input:
2 14 68 12 28 2 46
output:
-16
result:
ok found '-16.0000000', expected '-16.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 14116kb
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: 2ms
memory: 14112kb
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: 14076kb
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: 2ms
memory: 14168kb
input:
5 4 1 9 1 5 13 3 6 10 6 5 8 3 5 5
output:
9
result:
ok found '9.0000000', expected '9.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 2ms
memory: 14052kb
input:
5 3 7 9 5 7 12 4 6 13 3 6 6 2 1 2
output:
-6
result:
ok found '-6.0000000', expected '-6.0000000', error '-0.0000000'
Test #10:
score: 0
Accepted
time: 2ms
memory: 14016kb
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
result:
ok found '32.0000000', expected '32.0000000', error '0.0000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 14104kb
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
result:
ok found '12.0000000', expected '12.0000000', error '0.0000000'
Test #12:
score: 0
Accepted
time: 2ms
memory: 14140kb
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
result:
ok found '-6.0000000', expected '-6.0000000', error '-0.0000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 14108kb
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
result:
ok found '-5.0000000', expected '-5.0000000', error '-0.0000000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 14084kb
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
result:
ok found '21.0000000', expected '21.0000000', error '0.0000000'
Test #15:
score: 0
Accepted
time: 0ms
memory: 14076kb
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: 0ms
memory: 14080kb
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
result:
ok found '-100.0000000', expected '-100.0000000', error '-0.0000000'
Test #17:
score: 0
Accepted
time: 2ms
memory: 14100kb
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: 13988kb
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
result:
ok found '-57.0000000', expected '-57.0000000', error '-0.0000000'
Test #19:
score: 0
Accepted
time: 2ms
memory: 14016kb
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.5
result:
ok found '-81.5000000', expected '-81.5000000', error '-0.0000000'
Test #20:
score: -100
Wrong Answer
time: 33ms
memory: 23424kb
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:
2.10086e+06
result:
wrong answer 1st numbers differ - expected: '2100856.0000000', found: '2100860.0000000', error = '0.0000019'