oj.uz

Submission #810577

# Submission time Handle Problem Language Result Execution time Memory
810577 2023-08-06T11:31:53 Z caganyanmaz Seesaw (JOI22_seesaw) C++17
34 / 100
 2000 ms 37176 KB 
#include <bits/stdc++.h>
#define pb push_back

#define int int64_t
using namespace std;

constexpr static int INF = 3e14;
constexpr static double EPSILON = 0.000000000001;

constexpr static int MXSIZE = 5001;
int v[MXSIZE];
vector<double> vv[MXSIZE];
vector<double> all;

int32_t main()
{
        int n;
        cin >> n;
        for (int i = 0; i < n; i++)
                cin >> v[i];
        for (int l = 0; l < n; l++)
        {
                int sum = 0;
                for (int r = l+1; r <= n; r++)
                {
                        sum += v[r-1];
                        vv[r-l].pb(static_cast<double>(sum) / (r-l));
                        all.pb(vv[r-l].back());
                }
        }
        for (int i = 0; i <= n; i++)
                sort(vv[i].begin(), vv[i].end());
        double best = INF;
        for (double d : all)
        {
                double left = INF, right = 0;
                for (int i = 1; i <= n; i++)
                {
                        auto it = lower_bound(vv[i].begin(), vv[i].end(), d);
                        if (it == vv[i].end())
                        {
                                left = 0, right = INF;
                                break;
                        }
                        left = min(left, *it);
                        right = max(right, *it);
                }
                best = min(best, right - left);
        }
        cout << fixed;
        cout << setprecision(100);
        cout << best << "\n";
}

Subtask #1
1.0 / 1.0

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

Subtask #2
33.0 / 33.0

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

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 420 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 5 ms 548 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Execution timed out 2060 ms 37176 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 420 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 5 ms 548 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Execution timed out 2060 ms 37176 KB Time limit exceeded
9 Halted 0 ms 0 KB -