Submission #1274131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274131		Can_I_Put_ma_ballz	Seesaw (JOI22_seesaw)	C++20	0 / 100	2 ms	568 KiB

seesaw

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <iomanip>
using namespace std;

typedef long long ll;

struct Point {
    ll x, y;
    Point() {}
    Point(ll x, ll y) : x(x), y(y) {}
};

double slope(const Point& a, const Point& b) {
    return (double)(b.y - a.y) / (b.x - a.x);
}

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<ll> s(n + 1);
    s[0] = 0;
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + a[i - 1];
    }

    vector<double> C(n), D(n);
    for (int i = 0; i < n; i++) {
        C[i] = (double)s[i + 1] / (i + 1);
    }
    for (int i = 0; i < n; i++) {
        D[i] = (double)(s[n] - s[i]) / (n - i);
    }

    vector<double> minC(n), maxC(n);
    minC[n - 1] = C[n - 1];
    maxC[n - 1] = C[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        minC[i] = min(C[i], minC[i + 1]);
        maxC[i] = max(C[i], maxC[i + 1]);
    }

    vector<double> minD(n), maxD(n);
    minD[0] = D[0];
    maxD[0] = D[0];
    for (int i = 1; i < n; i++) {
        minD[i] = min(minD[i - 1], D[i]);
        maxD[i] = max(maxD[i - 1], D[i]);
    }

    vector<double> leftMin(n), leftMax(n);
    deque<Point> lowerHull, upperHull;

    for (int i = 0; i < n; i++) {
        Point newPoint(i, s[i]);

        while (lowerHull.size() >= 2) {
            Point last = lowerHull.back();
            Point secondLast = lowerHull[lowerHull.size() - 2];
            if (slope(secondLast, last) >= slope(last, newPoint)) {
                lowerHull.pop_back();
            } else {
                break;
            }
        }
        lowerHull.push_back(newPoint);

        Point queryPoint(i + 1, s[i + 1]);
        while (lowerHull.size() >= 2) {
            Point first = lowerHull[0];
            Point second = lowerHull[1];
            if (slope(first, queryPoint) >= slope(second, queryPoint)) {
                lowerHull.pop_front();
            } else {
                break;
            }
        }
        leftMin[i] = slope(lowerHull[0], queryPoint);

        while (upperHull.size() >= 2) {
            Point last = upperHull.back();
            Point secondLast = upperHull[upperHull.size() - 2];
            if (slope(secondLast, last) <= slope(last, newPoint)) {
                upperHull.pop_back();
            } else {
                break;
            }
        }
        upperHull.push_back(newPoint);

        while (upperHull.size() >= 2) {
            Point first = upperHull[0];
            Point second = upperHull[1];
            if (slope(first, queryPoint) <= slope(second, queryPoint)) {
                upperHull.pop_front();
            } else {
                break;
            }
        }
        leftMax[i] = slope(upperHull[0], queryPoint);
    }

    vector<ll> b(n);
    for (int i = 0; i < n; i++) {
        b[i] = a[n - 1 - i];
    }
    vector<ll> t(n + 1);
    t[0] = 0;
    for (int i = 1; i <= n; i++) {
        t[i] = t[i - 1] + b[i - 1];
    }

    vector<double> leftMin_rev(n), leftMax_rev(n);
    deque<Point> lowerHull_rev, upperHull_rev;

    for (int i = 0; i < n; i++) {
        Point newPoint(i, t[i]);
        while (lowerHull_rev.size() >= 2) {
            Point last = lowerHull_rev.back();
            Point secondLast = lowerHull_rev[lowerHull_rev.size() - 2];
            if (slope(secondLast, last) >= slope(last, newPoint)) {
                lowerHull_rev.pop_back();
            } else {
                break;
            }
        }
        lowerHull_rev.push_back(newPoint);

        Point queryPoint(i + 1, t[i + 1]);
        while (lowerHull_rev.size() >= 2) {
            Point first = lowerHull_rev[0];
            Point second = lowerHull_rev[1];
            if (slope(first, queryPoint) >= slope(second, queryPoint)) {
                lowerHull_rev.pop_front();
            } else {
                break;
            }
        }
        leftMin_rev[i] = slope(lowerHull_rev[0], queryPoint);

        while (upperHull_rev.size() >= 2) {
            Point last = upperHull_rev.back();
            Point secondLast = upperHull_rev[upperHull_rev.size() - 2];
            if (slope(secondLast, last) <= slope(last, newPoint)) {
                upperHull_rev.pop_back();
            } else {
                break;
            }
        }
        upperHull_rev.push_back(newPoint);

        while (upperHull_rev.size() >= 2) {
            Point first = upperHull_rev[0];
            Point second = upperHull_rev[1];
            if (slope(first, queryPoint) <= slope(second, queryPoint)) {
                upperHull_rev.pop_front();
            } else {
                break;
            }
        }
        leftMax_rev[i] = slope(upperHull_rev[0], queryPoint);
    }

    vector<double> rightMin(n), rightMax(n);
    for (int i = 0; i < n; i++) {
        rightMin[i] = leftMin_rev[n - 1 - i];
        rightMax[i] = leftMax_rev[n - 1 - i];
    }

    double ans = 1e18;
    for (int i = 0; i < n; i++) {
        double range1 = max(maxC[i], leftMax[i]) - min(minC[i], leftMin[i]);
        double range2 = max(maxD[i], rightMax[i]) - min(minD[i], rightMin[i]);
        ans = min(ans, min(range1, range2));
    }

    cout << fixed << setprecision(10) << ans << endl;

    return 0;
}

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