QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#111954 | #1880. Nikanor Loves Games | lingchen | WA | 2ms | 3748kb | C++14 | 2.0kb | 2023-06-09 11:16:08 | 2023-06-09 11:16:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define mkp make_pair
const int N=5e5+10;
const int M=1e6+10;
int n,m;
int a[N],b[N];ll x[N];
vector<int>li; map<int,int>ma;
ll f[M]; ll w[M];
ll pre[N],sum;
pair<int,int>res[N];
namespace task1{
void solve()
{
ll ans=-0x3f3f3f3f3f3f3f3f;
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++) ans=max(ans,f[i]+f[j]-4ll*li[i]*li[j]);
printf("%lld\n",ans);
}
}
namespace task2{
//b=val-f[a] k=-4a x=-b y=f[b]
db slope(int a,int b)
{
return (db)(f[b]-f[a])/(w[b]-w[a]);
}
int st[M],h,t;
void solve()
{
ll ans=-0x3f3f3f3f3f3f3f3f;
//printf("%lld\n",ans);
for(int i=1;i<=m;i++) w[i]=li[i];
h=1; st[++t]=1;
//ans=max(ans,f[1]+f[2]-4ll*w[1]*w[2]);
for(int i=2;i<=m;i++)
{
db k=(db)-4*w[i];
while(h<t&&k>=slope(st[h],st[h+1])) h++;
int j=st[h];
ans=max(ans,f[j]+f[i]-4ll*w[i]*w[j]);
while(h<t&&slope(st[t-1],i)<=slope(st[t-1],st[t])) t--;
st[++t]=i;
}
for(int i=1;i<=m;i++) ans=max(ans,f[i]+f[i]-4ll*w[i]*w[i]);
printf("%.10lf\n",ans/4.0);
}
}
int main()
{
//freopen("data3.in","r",stdin);
//freopen("test.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d%lld",&a[i],&b[i],&x[i]);
li.push_back(0); li.push_back(1);
for(int i=1;i<=n;i++) li.push_back(a[i]),li.push_back(b[i]);
sort(li.begin(),li.end());
li.erase(unique(li.begin(),li.end()),li.end());
m=(int)li.size()-1;
for(int i=1;i<=m;i++) ma[li[i]]=i;
for(int i=1;i<=n;i++) a[i]=ma[a[i]],b[i]=ma[b[i]];
for(int i=1;i<=n;i++) f[a[i]]+=2*x[i],f[b[i]]+=2*x[i],f[1]-=2*x[i];
for(int i=1;i<=m;i++) f[i]+=f[i-1];
//for(int i=1;i<=m;i++) printf("%lld ",li[i]);
//if(n<=2000) {task1::solve(); return 0;}
task2::solve(); fflush(stdout);
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3528kb
input:
2 1 4 15 3 5 10
output:
2.5000000000
result:
ok found '2.5000000', expected '2.5000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3620kb
input:
1 2 2 8
output:
4.0000000000
result:
ok found '4.0000000', expected '4.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3624kb
input:
3 94 68 49 51 2 63 26 85 20
output:
-73.0000000000
result:
ok found '-73.0000000', expected '-73.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
2 14 68 12 28 2 46
output:
-16.0000000000
result:
ok found '-16.0000000', expected '-16.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3560kb
input:
5 6 6 8 6 1 11 6 1 13 6 1 5 5 1 2
output:
9.5000000000
result:
ok found '9.5000000', expected '9.5000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3576kb
input:
5 5 4 2 4 1 10 3 1 3 2 1 3 5 1 5
output:
5.5000000000
result:
ok found '5.5000000', expected '5.5000000', error '0.0000000'
Test #7:
score: -100
Wrong Answer
time: 1ms
memory: 3684kb
input:
5 1 5 2 4 2 7 2 2 2 2 5 14 1 4 2
output:
2.0000000000
result:
wrong answer 1st numbers differ - expected: '4.5000000', found: '2.0000000', error = '0.5555556'