CSES - Putka Open 2015 – 5/6 - Results
Submission details
Task:Keskiarvo
Sender:
Submission time:2015-11-07 09:19:19 +0200
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED12
#2ACCEPTED17
#3ACCEPTED71
Test results
testverdicttimegroup
#1ACCEPTED0.06 s1details
#2ACCEPTED0.06 s1details
#3ACCEPTED0.05 s1details
#4ACCEPTED0.05 s1details
#5ACCEPTED0.06 s1details
#6ACCEPTED0.05 s2details
#7ACCEPTED0.06 s2details
#8ACCEPTED0.05 s2details
#9ACCEPTED0.05 s2details
#10ACCEPTED0.06 s2details
#11ACCEPTED0.05 s3details
#12ACCEPTED0.07 s3details
#13ACCEPTED0.06 s3details
#14ACCEPTED0.05 s3details
#15ACCEPTED0.07 s3details
#16ACCEPTED0.06 sdetails

Code

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
#include<utility>
#include<iomanip>

using namespace std;

typedef pair<int64_t,int64_t> P;

bool vasen(P p1, P p2, P p3) {
  return (p2.first - p1.first)*(p3.second - p1.second) - (p3.first - p1.first)*(p2.second - p1.second) > 0;
}

int main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  cout << fixed << setprecision(12);
  
  int64_t n;
  cin >> n;
  vector<int64_t> p(n+1);
  for(int64_t i=1;i<=n;i++) {
    int64_t b;
    cin >> b;
    p[i]=p[i-1]+b;
  }

  vector<pair<int64_t,int64_t>> a;
  a.push_back(make_pair(0,0));

  double best=0;

  for(int64_t i=1;i<=n;i++) {
    int c=a.size();
    while(c >= 2 && vasen(a[c-2], a[c-1], make_pair(i, p[i]))) {
      best=max(best,(double)(p[i] - a[a.size()-1].second) / (double)(i - a[a.size()-1].first));
      a.pop_back();
      c--;
    }
    a.push_back(make_pair(i, p[i]));
  }

  cout << best << '\n';
  
  return 0;
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
100
579911361 197658107 815676285 ...

correct output
980535539

user output
980535539.000000000000

Test 2

Group: 1

Verdict: ACCEPTED

input
100
541962319 20721724 733683610 9...

correct output
996955791

user output
996955791.000000000000

Test 3

Group: 1

Verdict: ACCEPTED

input
100
663677497 238679548 892011523 ...

correct output
978858928

user output
978858928.000000000000

Test 4

Group: 1

Verdict: ACCEPTED

input
100
754557795 14395441 943833407 1...

correct output
998391974

user output
998391974.000000000000

Test 5

Group: 1

Verdict: ACCEPTED

input
100
308690464 959776379 229201039 ...

correct output
995129158

user output
995129158.000000000000

Test 6

Group: 2

Verdict: ACCEPTED

input
100
752236199 201329268 457625816 ...

correct output
997456488

user output
997456488.000000000000

Test 7

Group: 2

Verdict: ACCEPTED

input
5000
314731332 844980432 427902587 ...

correct output
999901597

user output
999901597.000000000000

Test 8

Group: 2

Verdict: ACCEPTED

input
5000
520967279 915660277 633907984 ...

correct output
999938928

user output
999938928.000000000000

Test 9

Group: 2

Verdict: ACCEPTED

input
5000
989796225 185146611 419313583 ...

correct output
999908138

user output
999908138.000000000000

Test 10

Group: 2

Verdict: ACCEPTED

input
5000
510588037 414748990 635670363 ...

correct output
999894105

user output
999894105.000000000000

Test 11

Group: 3

Verdict: ACCEPTED

input
5000
312043025 563894859 350492609 ...

correct output
999944835

user output
999944835.000000000000

Test 12

Group: 3

Verdict: ACCEPTED

input
100000
92541013 71039803 247766345 34...

correct output
999984487

user output
999984487.000000000000

Test 13

Group: 3

Verdict: ACCEPTED

input
100000
423233870 652455282 139386372 ...

correct output
999994375

user output
999994375.000000000000

Test 14

Group: 3

Verdict: ACCEPTED

input
100000
559308968 52061073 826304361 9...

correct output
999989944

user output
999989944.000000000000

Test 15

Group: 3

Verdict: ACCEPTED

input
100000
425635648 182598452 773180708 ...

correct output
999996798

user output
999996798.000000000000

Test 16

Group:

Verdict: ACCEPTED

input
100000
90120093 590318798 59894256 89...

correct output
999999674

user output
999999674.000000000000