oj.uz

Submission #678270

# Submission time Handle Problem Language Result Execution time Memory
678270 2023-01-05T11:23:37 Z CodePlatina Seesaw (JOI22_seesaw) C++17
100 / 100
 60 ms 10848 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <tuple>
#include <iomanip>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define piii pair<int, pii>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
const int INF = (int)1e9 + 7;

using namespace std;

struct frac
{
    long long u, d;
    bool operator<(frac ot) const
    {
        return (__int128)u * ot.d < (__int128)ot.u * d;
    }
    operator long double() { return (long double)u / d; }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    int A[n]; for(auto &i : A) cin >> i;
    long long ps[n + 1]{}; for(int i = 1; i <= n; ++i) ps[i] = ps[i - 1] + A[i - 1];

    pair<frac, frac> B[n];
    B[0] = { {ps[n], n}, {ps[n], n} };
    for(int i = 1; i < n; ++i)
    {
        int s = 0, e = i;
        while(s + 1 < e)
        {
            int mid = s + e >> 1;
            if(frac{ps[n - i + mid] - ps[mid], n - i} < frac{ps[n], n}) s = mid;
            else e = mid;
        }
        B[i] = { frac{ps[n - i + s] - ps[s], n - i}, frac{ps[n - i + s + 1] - ps[s + 1], n - i} };
    }

    sort(B, B + n);
    frac r = B[n - 1].ff;
    long double ans = r - B[0].ff;
    for(int i = 0; i < n - 1; ++i)
    {
        r = max(r, B[i].ss);
        ans = min(ans, r - B[i + 1].ff);
    }
    r = max(r, B[n - 1].ss);
    ans = min(ans, r - B[n - 1].ff);

    cout << fixed << setprecision(20) << ans;
}

Compilation message

seesaw.cpp: In function 'int main()':
seesaw.cpp:47:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |             int mid = s + e >> 1;
      |                       ~~^~~

Subtask #1
1.0 / 1.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 324 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 376 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 376 KB Output is correct
12 Correct 52 ms 10804 KB Output is correct
13 Correct 60 ms 10840 KB Output is correct
14 Correct 51 ms 10840 KB Output is correct
15 Correct 51 ms 10792 KB Output is correct
16 Correct 51 ms 10848 KB Output is correct