QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#601754 | #1880. Nikanor Loves Games | rotcar07 | WA | 1ms | 5996kb | C++20 | 1.2kb | 2024-09-30 12:16:22 | 2024-09-30 12:16:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N=2e5+5;
int a[N],b[N],x[N],n,tp;
ll sum[N];int st[N];
typedef __int128 I;
int main(){
std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;vector<int> v;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i]>>x[i];
v.push_back(a[i]),v.push_back(b[i]);
}
v.push_back(0);
sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());
ll ans=-3e18;
for(int i=1;i<=n;i++){
sum[0]-=2*x[i];
sum[lower_bound(v.begin(),v.end(),a[i])-v.begin()]+=2*x[i];
sum[lower_bound(v.begin(),v.end(),b[i])-v.begin()]+=2*x[i];
}
int m=v.size()-1;
for(int i=1;i<=m;i++) sum[i]+=sum[i-1];
st[++tp]=m;
for(int i=m-1;~i;i--){
while(tp>1&&I(sum[i]-sum[st[tp]])*(v[st[tp]]-v[st[tp-1]])<=I(sum[st[tp]]-sum[st[tp-1]])*(v[i]-v[st[tp]])) tp--;
st[++tp]=i;
}
for(int i=m;~i;i--){
auto calc=[&](int w){return sum[i]+sum[w]-v[w]*4ll*v[i];};
while(tp>1&&calc(st[tp])<=calc(st[tp-1]))tp--;
ans=max(ans,calc(st[tp]));
}
cout<<fixed<<setprecision(10)<<ans/4.0<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5888kb
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: 1ms
memory: 5936kb
input:
1 2 2 8
output:
4.0000000000
result:
ok found '4.0000000', expected '4.0000000', error '0.0000000'
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 5996kb
input:
3 94 68 49 51 2 63 26 85 20
output:
0.0000000000
result:
wrong answer 1st numbers differ - expected: '-73.0000000', found: '0.0000000', error = '1.0000000'