QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#601753 | #1880. Nikanor Loves Games | rotcar07 | WA | 1ms | 8116kb | C++20 | 1.2kb | 2024-09-30 12:15:15 | 2024-09-30 12:15:16 |
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[1]-=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: 6064kb
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: 5780kb
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: 1ms
memory: 7972kb
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: 1ms
memory: 5960kb
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: 1ms
memory: 5792kb
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: 1ms
memory: 5840kb
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: 0
Accepted
time: 1ms
memory: 7884kb
input:
5 1 5 2 4 2 7 2 2 2 2 5 14 1 4 2
output:
4.5000000000
result:
ok found '4.5000000', expected '4.5000000', error '0.0000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 5844kb
input:
5 4 1 9 1 5 13 3 6 10 6 5 8 3 5 5
output:
9.0000000000
result:
ok found '9.0000000', expected '9.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 7872kb
input:
5 3 7 9 5 7 12 4 6 13 3 6 6 2 1 2
output:
-6.0000000000
result:
ok found '-6.0000000', expected '-6.0000000', error '-0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 5860kb
input:
10 8 10 26 11 2 28 13 4 13 11 1 26 6 15 23 12 8 7 9 8 11 11 10 17 8 11 18 3 10 27
output:
32.0000000000
result:
ok found '32.0000000', expected '32.0000000', error '0.0000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 5928kb
input:
10 6 5 10 10 15 21 7 2 30 14 6 12 1 11 6 1 13 19 8 13 29 9 4 14 1 4 29 4 12 17
output:
12.0000000000
result:
ok found '12.0000000', expected '12.0000000', error '0.0000000'
Test #12:
score: 0
Accepted
time: 1ms
memory: 5972kb
input:
10 5 15 15 3 14 20 11 14 26 15 12 22 5 15 11 12 10 10 1 12 18 7 7 14 3 5 10 12 9 23
output:
-6.0000000000
result:
ok found '-6.0000000', expected '-6.0000000', error '-0.0000000'
Test #13:
score: 0
Accepted
time: 1ms
memory: 5776kb
input:
10 3 9 29 9 5 27 14 13 21 3 15 15 14 11 24 9 14 22 9 3 20 12 15 27 5 13 21 13 11 14
output:
-5.0000000000
result:
ok found '-5.0000000', expected '-5.0000000', error '-0.0000000'
Test #14:
score: 0
Accepted
time: 1ms
memory: 8116kb
input:
10 3 13 11 3 5 20 9 10 1 5 5 25 10 1 29 6 10 26 1 15 1 10 10 18 6 6 2 14 6 20
output:
21.0000000000
result:
ok found '21.0000000', expected '21.0000000', error '0.0000000'
Test #15:
score: 0
Accepted
time: 1ms
memory: 5836kb
input:
100 68 91 90 56 38 71 69 57 87 80 62 21 31 80 25 36 48 40 71 66 49 15 57 78 96 69 43 25 73 57 86 13 5 23 98 18 83 94 9 8 22 43 46 3 50 81 11 26 14 35 39 49 68 73 41 11 25 35 47 48 5 96 15 15 56 60 42 1 40 11 4 25 57 72 9 43 3 90 16 45 36 83 50 17 55 40 39 72 37 6 70 84 24 12 36 95 43 15 13 82 28 68 ...
output:
35.5000000000
result:
ok found '35.5000000', expected '35.5000000', error '0.0000000'
Test #16:
score: -100
Wrong Answer
time: 1ms
memory: 7972kb
input:
100 92 35 39 34 92 36 45 45 46 66 5 64 22 21 48 53 70 91 93 19 98 97 67 54 57 77 64 90 81 23 12 83 92 59 3 26 13 65 47 19 23 58 27 58 38 60 18 70 32 94 53 100 66 97 33 53 16 56 2 64 8 9 55 93 92 22 27 25 39 45 49 24 76 80 89 73 55 77 69 53 90 39 77 40 86 12 11 23 87 25 8 96 31 73 45 98 52 62 55 98 9...
output:
-168.0000000000
result:
wrong answer 1st numbers differ - expected: '-100.0000000', found: '-168.0000000', error = '0.6800000'