QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #34051 | #1880. Nikanor Loves Games | moyujiang | WA | 3ms | 8000kb | C++ | 1.4kb | 2022-06-05 15:51:39 | 2022-06-05 15:51:40 |
Judging History
answer
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define Rof(i,b,a) for(int i=(b),i##END=(a);i>=i##END;i--)
#define go(u) for(int i=head[u];i;i=nxt[i])
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=2e6+10;
#define fi first
#define se second
int n,m,sum,c;
map<int,int> mp;
int val[N],id[N];
struct node{
int x,y;
int val(int a){return x*a+y;}
}q[N];int L,R;
//bool check(node A,node B,node C){
// int x1=B.x-A.x,y1=B.y-A.y,x2=C.x-B.x,y2=C.y-B.y;
// return x1*y2-x2*y1>0;
//}
bool check(node A,node B,node C){//(k,b)
return (B.y-A.y)*(C.x-B.x)>(C.y-B.y)*(B.x-A.x);
}
signed main(){
n=read();
For(i,1,n){
int u=read(),v=read(),x=read();
mp[u]+=x,mp[v]+=x,sum-=2*x;
}for(auto x:mp)c++,id[c]=x.fi*2,sum+=2*x.se,val[c]=sum;
int ans=-1e18;
// For(i,1,c)For(j,i,c)ans=max(ans,val[i]+val[j]-id[i]*id[j]);
L=1,R=0;For(i,1,c){
node now=(node){id[i],val[i]};
while(L<R&&!check(q[R-1],q[R],now))R--;
q[++R]=now;
}For(i,1,c){
ans=max(ans,2*val[i]-id[i]*id[i]);
while(L<R&&q[R-1].val(-id[i])>=q[R].val(-id[i]))R--;
ans=max(ans,val[i]+q[R].val(-id[i]));
}
cout<<1.0*ans/4<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 7996kb
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: 7936kb
input:
1 2 2 8
output:
4
result:
ok found '4.0000000', expected '4.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 3ms
memory: 7896kb
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: 2ms
memory: 7816kb
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: 1ms
memory: 7948kb
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: 8000kb
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: 7824kb
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: 7804kb
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: 3ms
memory: 7900kb
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: 7788kb
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: 7736kb
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: 7804kb
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: 2ms
memory: 8000kb
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: 2ms
memory: 7952kb
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: 2ms
memory: 7864kb
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: -100
Wrong Answer
time: 2ms
memory: 7900kb
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:
-168
result:
wrong answer 1st numbers differ - expected: '-100.0000000', found: '-168.0000000', error = '0.6800000'