oj.uz

Submission #677712

# Submission time Handle Problem Language Result Execution time Memory
677712 2023-01-04T08:15:40 Z benedict0724 Seesaw (JOI22_seesaw) C++17
1 / 100
 1 ms 212 KB 
#include <iostream>
#include <stack>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cassert>

using namespace std;
typedef long long ll;

double A[200002];
int N;

double solve(int i, double now)
{
    double l, r;
    l = min(A[i], now);
    r = max(A[i], now);
    int s = 1, e = N;
    for(int i=1;i<N;i++)
    {
        double S = (now * (N - i + 1) - A[s]) / (N - i);
        double E = (now * (N - i + 1) - A[e]) / (N - i);
        
        if(max(r, S) - min(l, S) <= max(r, E) - min(l, E))
        {
            now = S;
            s++;
        }
        else
        {
            now = E;
            e--;
        }
        r = max(r, now);
        l = min(l, now);
    }
    return r - l;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin >> N;
    for(int i=1;i<=N;i++) cin >> A[i];
    double now = 0;
    for(int i=1;i<=N;i++) now += A[i];
    now /= N;
    double ans = A[N] - A[1];
    for(int i=1;i<=N;i++) ans = min(ans, solve(i, now));
    cout.precision(15);
    cout << ans;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -