oj.uz

Submission #698468

# Submission time Handle Problem Language Result Execution time Memory
698468 2023-02-13T14:36:59 Z Duy_e Seesaw (JOI22_seesaw) C++14
34 / 100
 465 ms 293208 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair <ll, ll>
#define nd second
#define st first
#define rep(i, n, m) for (ll i = (n); i <= (m); i ++)
#define rrep(i, n, m) for (ll i = (n); i >= (m); i --);
using namespace std;

const long long N = 2e6 + 7;

ll n, a[N], s[N], b[N];

struct fract {
    ll x, y;
    fract() {}
    fract(ll _x, ll _y) {
        ll g = __gcd(_x, _y);
        x = _x / g; y = _y / g;
    }
    bool operator <(fract other) {
        return (long double)x / y < (long double)other.x / other.y;
    }
    bool operator ==(fract other) {
        return x == other.x && y == other.y;
    }
} c[N];

fract operator -(fract x, fract y) {
    return fract(x.x * y.y - x.y * y.x, x.y * y.y);
}

vector <int> d[N];
int cv(int i, int j) {
    return (i - 1) * n + j;
}

bool vis[N], ck[N];

bool dfs(int u, int l, int r) {
    if (b[u] < l || b[u] > r) return false;
    if (ck[u]) return true;
    vis[u] = true;
    for (int v: d[u]) {
        if (!vis[v] && dfs(v, l, r))
            return true;
    }
    return false;
}

int main() {
    ios_base :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);

    cin >> n;
    rep(i, 1, n) cin >> a[i], s[i] = s[i - 1] + a[i];

    vector <fract> lmt;
    rep(i, 1, n) rep(j, i, n) {
        int u = cv(i, j);
        lmt.push_back(fract(s[j] - s[i - 1], j - i + 1));
        c[u] = lmt.back();
        if (i == j) continue;
        d[u].push_back(cv(i + 1, j));
        d[u].push_back(cv(i, j - 1));
    }

    sort(lmt.begin(), lmt.end());
    lmt.resize(unique(lmt.begin(), lmt.end()) - lmt.begin());

    rep(i, 1, n) rep(j, i, n) {
        int u = cv(i, j);
        fract x = c[u];
        b[u] = lower_bound(lmt.begin(), lmt.end(), x) - lmt.begin();
    }

    rep(i, 1, n) ck[cv(i, i)] = true;

    int l = 0;
    fract ans(1e9, 1);
    rep(r, 0, (int)lmt.size() - 1) {
        while (l <= r && dfs(cv(1, n), l, r)) {
            fract tmp = lmt[r] - lmt[l];
            if (tmp < ans)
                ans = tmp;
            l ++;
            memset(vis, 0, sizeof vis);
        }
        memset(vis, 0, sizeof vis);
    }

    cout << setprecision(20) << fixed << (long double)ans.x / ans.y;

    return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 49280 KB Output is correct
2 Correct 37 ms 49236 KB Output is correct
3 Correct 39 ms 49288 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 49280 KB Output is correct
2 Correct 37 ms 49236 KB Output is correct
3 Correct 39 ms 49288 KB Output is correct
4 Correct 372 ms 49712 KB Output is correct
5 Correct 465 ms 49740 KB Output is correct
6 Correct 374 ms 49816 KB Output is correct
7 Correct 353 ms 49736 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 49280 KB Output is correct
2 Correct 37 ms 49236 KB Output is correct
3 Correct 39 ms 49288 KB Output is correct
4 Correct 372 ms 49712 KB Output is correct
5 Correct 465 ms 49740 KB Output is correct
6 Correct 374 ms 49816 KB Output is correct
7 Correct 353 ms 49736 KB Output is correct
8 Runtime error 358 ms 293208 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 49280 KB Output is correct
2 Correct 37 ms 49236 KB Output is correct
3 Correct 39 ms 49288 KB Output is correct
4 Correct 372 ms 49712 KB Output is correct
5 Correct 465 ms 49740 KB Output is correct
6 Correct 374 ms 49816 KB Output is correct
7 Correct 353 ms 49736 KB Output is correct
8 Runtime error 358 ms 293208 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -