QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#42925 | #1880. Nikanor Loves Games | HBWH_zzz_std | WA | 3ms | 11884kb | C++ | 2.5kb | 2022-08-05 10:00:47 | 2022-08-05 10:00:49 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp std::make_pair
#define pii std::pair<ll,ll>
#define chkmin(_A,_B) (_A=std::min(_A,_B))
#define chkmax(_A,_B) (_A=std::max(_A,_B))
class IO{
public:
inline char read(){
static const int IN_LEN =1<<18|1;
static char buf[IN_LEN],*s,*t;
return (s==t)&&(t=(s=buf)+fread(buf, 1, IN_LEN, stdin)),(s==t)?-1:*s++;
}
template<typename _Tp>inline IO &operator >>(_Tp &x){
static char c11, boo;
for (c11=read(),boo=0;!isdigit(c11);c11=read()) {
if (c11==-1)
return *this;
boo|=(c11=='-');
}
for(x=0;isdigit(c11);c11=read())
x=x*10+(c11^'0');
if(boo)
x=-x;
return *this;
}
inline void push(const char &c) {
putchar(c);
}
template<typename _Tp>inline IO &operator <<( _Tp x){
if (x<0)
x=-x,push('-');
static _Tp sta[35];
_Tp top=0;
do{
sta[top++]=x%10,x/=10;
}while(x);
while(top)
push(sta[--top]+'0');
return *this;
}
inline IO &operator <<(char lastChar){
push(lastChar);
return *this;
}
}FIO;
int n,tot;
ll pre[1000005],suf[1000005];
pii a[1000005];
int q[1000005],l,r;
ll ans=-1e14;
ll X(int _x){return a[_x].first;}
ll Y(int _x){return pre[_x]-suf[_x];}
double slope(int _x,int _y){return (double)(Y(_x)-Y(_y))/(double)(X(_x)-X(_y));}
ll res(int _x,int _y){return (Y(_x))+(Y(_y))-(X(_x)*(X(_y)));}
int cmp(const pii &A,const pii &B){
return (A.first==B.first)?A.second>B.second:A.first<B.first;
}
int main(){
FIO>>n;
for(int i=1;i<=n;++i){
ll ai,bi,xi;
FIO>>ai>>bi>>xi;
a[++tot]=mp(ai*2,xi);
a[++tot]=mp(bi*2,xi);
}
a[++tot]=mp(2,0);
sort(a+1,a+tot+1,cmp);
n=tot;
for(int i=1;i<=n;++i)
pre[i]=pre[i-1]+a[i].second;
for(int i=n;i>=1;--i)
suf[i]=suf[i+1]+a[i+1].second;
l=1;r=1;
q[1]=1;
/*
for(int i=1;i<=n;++i){
FIO<<X(i)<<' '<<Y(i)<<'\n';
}
*/
for(int i=2;i<=n;++i){
while(l<r && res(i,q[r])<=res(i,q[r-1]))
r--;
chkmax(ans,res(i,q[r]));
while(l<r && slope(q[r-1],q[r])<=slope(q[r],i))
r--;
q[++r]=i;
}
for(int i=1;i<=n;++i)
chkmax(ans,res(i,i));
printf("%lf",(double)ans/4.0);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 9936kb
input:
2 1 4 15 3 5 10
output:
2.500000
result:
ok found '2.5000000', expected '2.5000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 11884kb
input:
1 2 2 8
output:
4.000000
result:
ok found '4.0000000', expected '4.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 2ms
memory: 9864kb
input:
3 94 68 49 51 2 63 26 85 20
output:
-73.000000
result:
ok found '-73.0000000', expected '-73.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 9868kb
input:
2 14 68 12 28 2 46
output:
-16.000000
result:
ok found '-16.0000000', expected '-16.0000000', error '-0.0000000'
Test #5:
score: -100
Wrong Answer
time: 2ms
memory: 11880kb
input:
5 6 6 8 6 1 11 6 1 13 6 1 5 5 1 2
output:
3.000000
result:
wrong answer 1st numbers differ - expected: '9.5000000', found: '3.0000000', error = '0.6842105'