QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#39937 | #4355. Seesaw | ZeinDaner | 0 | 4ms | 7816kb | C++ | 1.3kb | 2022-07-15 00:40:12 | 2022-07-15 00:40:13 |
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;
int X[3]={-1,0};
int Y[3]={0,1};
vector<int> x;
int n;
double pre[2010][2010];
double dis[2010][2010];
double bfs(double miw){
queue<ii> q;
for(int i=0;i<n;i++){
if(x[i]>=miw) q.push(ii(i,i));
}
while(!q.empty()){
int xi=q.front().first,yi=q.front().second;
q.pop();
for(int i=0;i<2;i++){
int xk=xi+X[i];
int yk=yi+Y[i];
if(xk>=0 && yk<n && pre[xk][yk]>=miw){
if(dis[xk][yk]>=max(pre[xk][yk],dis[xi][yi])){
dis[xk][yk]=max(pre[xk][yk],dis[xi][yi]);
q.push(ii(xk,yk));
}
}
}
}
return dis[0][n-1]-miw;
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
int a; scanf("%d",&a);
x.push_back(a);
}
set<double> ord;
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);
ord.insert(-pre[i][j]);
}
}
for(int i=0;i<n;i++){
dis[i][i]=pre[i][i];
for(int j=i+1;j<n;j++){
dis[i][j]=MAX;
}
}
double ans=MAX;
for(auto &v:ord){
ans=min(ans,bfs(-v));
}
printf("%.12f\n",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 1
Accepted
time: 3ms
memory: 5924kb
input:
2 925278587 966813970
output:
20767691.500000000000
result:
ok found '20767691.500000000', expected '20767691.500000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 4ms
memory: 5852kb
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: -1
Wrong Answer
time: 2ms
memory: 7816kb
input:
20 37698309 122861191 172244451 227579326 314637638 425599056 429200117 531049382 548293537 557767688 600249369 625965962 703410128 707452380 747227710 753853272 821738507 858449772 859150731 988518805
output:
11481196.000000000000
result:
wrong answer 1st numbers differ - expected: '37041534.6529411', found: '11481196.0000000', error = '0.6900453'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%