Submission #677955

#	Time	Username	Problem	Language	Result	Execution time	Memory
677955		qwerasdfzxcl	Seesaw (JOI22_seesaw)	C++17	67 / 100	1100 ms	133444 KiB

seesaw

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct Frac{
    ll a, b;
    Frac(){}
    Frac(ll _a, ll _b): a(_a), b(_b) {}

    long double ch()const{return (long double) a / b;}

    bool operator < (const Frac &F) const{
        return (__int128)a * F.b < (__int128)b * F.a;
    }
}val[2020][2020];

int n, a[200200], idx[200200];
set<pair<Frac, int>> st;

int main(){
    scanf("%d", &n);
    for (int i=1;i<=n;i++) scanf("%d", a+i);

    for (int i=1;i<=n;i++){
        val[i][i] = Frac(a[i], 1);
        for (int j=i+1;j<=n;j++){
            val[i][j].a = val[i][j-1].a + a[j];
            val[i][j].b = j-i+1;
        }
    }

    for (int d=0;d<=n-1;d++){
        for (int i=n-d;i;i--){
            int j = i+d;
            if (i==1 || val[i][j] < val[1][n]){
                st.emplace(val[i][j], d);
                idx[d] = i;
                break;
            }
        }
    }

    long double ans = 1e18;

    while(!st.empty()){
        ans = min(ans, st.rbegin()->first.ch() - st.begin()->first.ch());

        auto [x, d] = *st.begin();
        st.erase(st.begin());
        //printf("%Lf %d\n", x.ch(), d);
        if (idx[d]+1+d > n) break;

        st.emplace(val[idx[d]+1][idx[d]+1+d], d);


    }

    printf("%.15Lf\n", ans);
    return 0;
}

Compilation message (stderr)

seesaw.cpp: In function 'int main()':
seesaw.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
seesaw.cpp:22:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     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: 0 / 33