QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#39935 | #4355. Seesaw | ZeinDaner | 1 | 3ms | 5992kb | C++ | 1.2kb | 2022-07-14 23:28:59 | 2022-07-14 23:29:02 |
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=pre[0][n-1];
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));
}
詳細信息
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 1ms
memory: 3720kb
input:
2 925278587 966813970
output:
20767691.500000000000
result:
ok found '20767691.500000000', expected '20767691.500000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
20 7902238 121690240 160345001 255257832 269315023 288280211 296247186 353929891 494812700 530994847 567379029 567478415 612943598 644028258 654380821 696407711 708542915 738196686 743020754 760907139
output:
52991294.166666686535
result:
ok found '52991294.166666687', expected '52991294.166666687', error '0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
20 37698309 122861191 172244451 227579326 314637638 425599056 429200117 531049382 548293537 557767688 600249369 625965962 703410128 707452380 747227710 753853272 821738507 858449772 859150731 988518805
output:
37041534.652941107750
result:
ok found '37041534.652941108', expected '37041534.652941108', error '0.000000000'
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #4:
score: 0
Wrong Answer
time: 3ms
memory: 5992kb
input:
100 3062543 14271669 41756258 53160546 58687738 65412641 67125846 67682424 88351830 97353987 99930389 104312394 110237749 130302887 144473978 192578518 199299154 202189413 203221174 206103152 207626225 248318304 251935772 253594311 255555599 258718911 280683793 291873353 296119011 303038714 30679761...
output:
12567914.329999983311
result:
wrong answer 1st numbers differ - expected: '10402282.1366460', found: '12567914.3300000', error = '0.2081882'
Subtask #3:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%