QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#721227#1880. Nikanor Loves GamesNt_YesterWA 1ms10100kbC++201.3kb2024-11-07 15:37:362024-11-07 15:37:37

Judging History

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

  • [2024-11-07 15:37:37]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:10100kb
  • [2024-11-07 15:37:36]
  • 提交

answer

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

#define N 1000005
#define LL long long
#define INF 0x3f3f3f3f3f3f3f3f

inline int R() {
    int x=0; bool f=0; char c=getchar();
    while (!isdigit(c)) f|=(c=='-'),c=getchar();
    while (isdigit(c)) x=x*10+c-'0',c=getchar();
    return f?-x:x;
}

template<typename T>
void W(T x,int op=0) {
    if (x<0) return putchar('-'),W(-x,op);
    if (x>9) W(x/10); putchar(x%10+'0');
    if (op) putchar(op==1?' ':'\n');
}

using namespace std;
int n,a[N],b[N],x[N],k,c[N]; LL sum[N];

int main() {
    // freopen("b.in","r",stdin);
    n=R();
    for (int i=1;i<=n;i++)
        c[++k]=a[i]=R(),c[++k]=b[i]=R(),x[i]=R();
    c[++k]=1; LL Sum=0;
    sort(c+1,c+k+1); k=unique(c+1,c+k+1)-c-1;
    for (int i=1;i<=n;i++) {
        a[i]=lower_bound(c+1,c+k+1,a[i])-c;
        b[i]=lower_bound(c+1,c+k+1,b[i])-c;
        sum[a[i]]+=x[i],sum[b[i]]+=x[i],Sum+=2*x[i];
    }
    for (int i=1;i<=k;i++) sum[i]+=sum[i-1];
    for (int i=1;i<=k;i++) sum[i]=2*sum[i]-Sum;
    LL ans=-INF;
    for (int i=1,j=k;i<=k;i++) {
        while (j>1 and sum[j]-4ll*c[i]*c[j]<sum[j-1]-4ll*c[i]*c[j-1]) --j;
        ans=max(ans,sum[i]+sum[j]-4ll*c[i]*c[j]);
    }
    // W(ans,2);
    printf("%.7lf\n",ans/4.0);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 10100kb

input:

2
1 4 15
3 5 10

output:

2.5000000

result:

ok found '2.5000000', expected '2.5000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 9840kb

input:

1
2 2 8

output:

4.0000000

result:

ok found '4.0000000', expected '4.0000000', error '0.0000000'

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 10032kb

input:

3
94 68 49
51 2 63
26 85 20

output:

-94.0000000

result:

wrong answer 1st numbers differ - expected: '-73.0000000', found: '-94.0000000', error = '0.2876712'