QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#42925#1880. Nikanor Loves GamesHBWH_zzz_stdWA 3ms11884kbC++2.5kb2022-08-05 10:00:472022-08-05 10:00:49

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-05 10:00:49]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:11884kb
  • [2022-08-05 10:00:47]
  • 提交

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;
}

詳細信息

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'