Submission #677749

#	Time	Username	Problem	Language	Result	Execution time	Memory
677749		puppy	Seesaw (JOI22_seesaw)	C++17	67 / 100	175 ms	39380 KiB

seesaw

#include <bits/stdc++.h>
#define double long double
#define int long long
using namespace std;
struct avg
{
    pair<int, int> p;
    int l, r;
    bool operator < (const avg &c) const {
        return p.first * c.p.second < p.second * c.p.first;
    }
};
int arr[2005];
int s[2005];
pair<int, int> dp[2005][2005];
double diff(multiset<avg> &st)
{
    pair<int, int> high = (*--st.end()).p;
    double h = (double)high.first / high.second;
    pair<int, int> low = (*st.begin()).p;
    double l = (double)low.first / low.second;
    return h - l;
}
signed main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        s[i] = s[i-1] + arr[i];
    }
    multiset<avg> st;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n - i + 1; j++) {
            //(j, j + i - 1) 범위
            dp[i][j] = make_pair(s[j+i-1] - s[j-1], i);
        }
    }
    for (int i = 1; i <= n; i++) {
        avg av = {dp[i][1], i, 1};
        st.insert(av);
    }
    double ans = 1e9;
    while (1) {
        ans = min(ans, diff(st));
        auto it = st.begin();
        if ((*it).l + (*it).r == n + 1) {
            break;
        }
        avg av = *it; st.erase(it);
        int newi = av.l;
        int newj = av.r + 1;
        av = {dp[newi][newj], newi, newj};
        st.insert(av);
    }
    cout.precision(10);
    cout << fixed;
    cout << ans << '\n';
}

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