QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#39932#4355. SeesawZeinDaner0 2ms3716kbC++1.1kb2022-07-14 23:21:222022-07-14 23:21:23

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-14 23:21:23]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:3716kb
  • [2022-07-14 23:21:22]
  • 提交

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%