oj.uz

Submission #677749

# Submission time Handle Problem Language Result Execution time Memory
677749 2023-01-04T09:39:00 Z puppy Seesaw (JOI22_seesaw) C++17
67 / 100
 175 ms 39380 KB 
#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.0 / 1.0

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

Subtask #2
33.0 / 33.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 170 ms 39380 KB Output is correct
9 Correct 169 ms 39380 KB Output is correct
10 Correct 175 ms 39380 KB Output is correct
11 Correct 175 ms 39380 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 170 ms 39380 KB Output is correct
9 Correct 169 ms 39380 KB Output is correct
10 Correct 175 ms 39380 KB Output is correct
11 Correct 175 ms 39380 KB Output is correct
12 Runtime error 2 ms 468 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -