QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #34041 | #1880. Nikanor Loves Games | moyujiang | WA | 3ms | 8000kb | C++ | 1.4kb | 2022-06-05 15:30:40 | 2022-06-05 15:30: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].val(-id[i])>=q[R-1].val(-id[i]))R--;
ans=max(ans,val[i]+q[R].val(-id[i]));
}
cout<<1.0*ans/4<<endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 7796kb
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: 7872kb
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: 7860kb
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: 3ms
memory: 8000kb
input:
2 14 68 12 28 2 46
output:
-16
result:
ok found '-16.0000000', expected '-16.0000000', error '-0.0000000'
Test #5:
score: -100
Wrong Answer
time: 2ms
memory: 7784kb
input:
5 6 6 8 6 1 11 6 1 13 6 1 5 5 1 2
output:
3
result:
wrong answer 1st numbers differ - expected: '9.5000000', found: '3.0000000', error = '0.6842105'