Submission #643750

#	Time	Username	Problem	Language	Result	Execution time	Memory
643750		Pajaraja	Seesaw (JOI22_seesaw)	C++17	100 / 100	49 ms	8224 KiB

seesaw

#include <bits/stdc++.h>
#define MAXN 200007
using namespace std;
pair<double,double> db[MAXN];
long long a[MAXN],p[MAXN];
double avg, ry[MAXN],sol=1000000000.0;
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 (stderr)

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

• Subtask 1: 1 / 1
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 33 / 33