QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#26553 | #1880. Nikanor Loves Games | Crysfly# | WA | 3ms | 15992kb | C++11 | 1.7kb | 2022-04-07 18:34:01 | 2022-04-29 03:57:43 |
Judging History
answer
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define int long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define x first
#define y second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 2000005
#define inf 0x3f3f3f3f
int n,res;
int a[maxn],b[maxn],x[maxn];
int t[maxn],len,y[maxn];
int c[maxn];
pii stk[maxn];
int top;
void ins(int x,int y){
while(top>1 && (y-stk[top].y)*(stk[top].x-stk[top-1].x) > (stk[top].y-stk[top-1].y)*(x-stk[top].x)) --top;
stk[++top]=mkp(x,y);
}
inline int F(pii f,int x){
return f.y-x*f.x;
}
signed main()
{
n=read();
For(i,1,n){
a[i]=read(),b[i]=read(),x[i]=read();
if(a[i]>b[i])swap(a[i],b[i]);
t[++len]=a[i],t[++len]=b[i];
}
sort(t+1,t+len+1),len=unique(t+1,t+len+1)-t-1;
int now=0;
For(i,1,n)now-=x[i];
res=now;
For(i,1,n){
int p=lower_bound(t+1,t+len+1,a[i])-t;
c[p]+=x[i];
p=lower_bound(t+1,t+len+1,b[i])-t;
c[p]+=x[i];
}
ins(0,now);
For(i,1,len){
now+=c[i];
y[i]=now;
cout<<t[i]<<' '<<y[i]<<endl;
ins(t[i],y[i]);
}
int pos=top;
For(i,1,len){
// A = t[i]
while(pos>1 && F(stk[pos-1],2*t[i])>=F(stk[pos],2*t[i])) --pos;
// cout<<"ans: "<<t[i]<<' '<<stk[pos].x<<' '<<y[i]+F(stk[pos],2*t[i])<<endl;
res=max(res,y[i]+F(stk[pos],2*t[i]));
}
printf("%lld.%lld",res>>1,(res%2)*5);
return 0;
}
/*
a<a[i] -x/2
a[i]<=a<b[i] 0
b[i]>=a x/2
f(A) + f(B) - 2*A*B
枚举 A
tmp + F(B) - A*B
*/
詳細信息
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 15992kb
input:
2 1 4 15 3 5 10
output:
1 -10 3 0 4 15 5 25 2.5
result:
wrong answer 1st numbers differ - expected: '2.5000000', found: '1.0000000', error = '0.6000000'