QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#39935#4355. SeesawZeinDaner1 3ms5992kbC++1.2kb2022-07-14 23:28:592022-07-14 23:29:02

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:29:02]
  • 评测
  • 测评结果:1
  • 用时:3ms
  • 内存:5992kb
  • [2022-07-14 23:28:59]
  • 提交

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));
}

Details

Tip: Click on the bar to expand more detailed information

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%