QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#39932 | #4355. Seesaw | ZeinDaner | 0 | 2ms | 3716kb | C++ | 1.1kb | 2022-07-14 23:21:22 | 2022-07-14 23:21:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<double,double> dd;
typedef pair<ii,dd> iidd;
const int MAX_N=2e5+10;
const int MAX=1e9+1;
vector<int> x;
int n;
double pre[2010][2010];
double cost(double lm){
int l=0,r=n-1;
double ma=pre[0][n-1];
for(int i=0;i<n-1;i++){
if(pre[l+1][r]>=lm && pre[l][r-1]>=lm){
if(pre[l+1][r]>pre[l][r-1])
r--;
else l++;
}
else{
if(pre[l+1][r]>=lm)
l++;
else{
if(pre[l][r-1]>=lm) r--;
else return MAX;
}
}
ma=max(ma,pre[l][r]);
}
return ma-lm;
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
int a; scanf("%d",&a);
x.push_back(a);
}
for(int i=0;i<n;i++){
ll sum=0;
double c=0;
for(int j=i;j<n;j++){
c++;
sum+=x[j];
pre[i][j]=(sum/c);
}
}
double l=0,r=MAX;
for(int i=0;i<=100;i++){
double m1=l+(r-l)/3;
double m2=r-(r-l)/3;
double c1=cost(m1);
double c2=cost(m2);
if(c1>c2) l=m1;
if(c2>c1) r=m2;
if(c1==c2){
l=m1; r=m2;
}
}
printf("%.12f\n",cost(l));
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3716kb
input:
2 925278587 966813970
output:
0.000000000000
result:
wrong answer 1st numbers differ - expected: '20767691.5000000', found: '0.0000000', error = '1.0000000'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%