oj.uz

Submission #871010

# Submission time Handle Problem Language Result Execution time Memory
871010 2023-11-09T17:16:14 Z Trisanu_Das Seesaw (JOI22_seesaw) C++17
100 / 100
 43 ms 10172 KB 
#include <bits/stdc++.h>
using namespace std;

pair<double,double> db[200005];
long long a[200005],p[200005];
double avg, ry[200005], sol = DBL_MAX;

double intervalavg(int l,int r) {return (p[r]-p[l-1])/(r-l+1.0);}

int binarna(int l,int r,int k) {
    if(l==r) return l;
    int s=(l+r)/2;
    if(intervalavg(s,s+k)<avg) return binarna(s+1,r,k);
    else return binarna(l,s,k);
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) p[i]=p[i-1]+a[i];
    avg=p[n]/(1.0*n);
    for(int i=0;i<n-1;i++)
    {
        int ind=binarna(1,n-i,i);
        db[i]={intervalavg(ind,ind+i)-avg,avg-intervalavg(ind-1,ind+i-1)};
    }
    db[n-1]={0,0};
    sort(db,db+n);
    for(int i=n-1;i>=0;i--) ry[i]=max(ry[i+1],db[i].second);
    for(int i=0;i<n;i++) sol=min(sol,db[i].first+ry[i+1]);
    printf("%.10f",sol);
}

Compilation message

seesaw.cpp: In function 'int main()':
seesaw.cpp:21:35: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   21 |     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
      |                                  ~^  ~~~~~
      |                                   |  |
      |                                   |  long long int*
      |                                   int*
      |                                  %lld
seesaw.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
seesaw.cpp:21:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
      |                           ~~~~~^~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 39 ms 8068 KB Output is correct
13 Correct 42 ms 10144 KB Output is correct
14 Correct 40 ms 10172 KB Output is correct
15 Correct 43 ms 10016 KB Output is correct
16 Correct 42 ms 10152 KB Output is correct