oj.uz

Submission #698467

# Submission time Handle Problem Language Result Execution time Memory
698467 2023-02-13T14:30:39 Z Duy_e Seesaw (JOI22_seesaw) C++14
0 / 100
 1 ms 1364 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 = 2e2 + 7;

ll n, a[N], s[N], b[N * 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 x * other.y < y * other.x;
    }
    bool operator ==(fract other) {
        return x == other.x && y == other.y;
    }
} c[N * 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 * N];
int cv(int i, int j) {
    return (i - 1) * n + j;
}

bool vis[N * N], ck[N * 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) {
        lmt.push_back(fract(s[j] - s[i - 1], j - i + 1));
        c[cv(i, j)] = lmt.back();
    }

    sort(lmt.begin(), lmt.end());
    lmt.resize(unique(lmt.begin(), lmt.end()) - lmt.begin());
    cout << setprecision(10) << fixed;
    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();
        if (i == j) continue;
        d[u].push_back(cv(i + 1, j));
        d[u].push_back(cv(i, j - 1));
    }

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

    int l = 0;
    fract ans(1e9, 1);
    rep(r, 0, 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);
        }
    }

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

    return 0;
}

Compilation message

seesaw.cpp: In function 'int main()':
seesaw.cpp:6:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<fract>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define rep(i, n, m) for (ll i = (n); i <= (m); i ++)
      |                                         ^
seesaw.cpp:83:5: note: in expansion of macro 'rep'
   83 |     rep(r, 0, lmt.size() - 1) {
      |     ^~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Incorrect 1 ms 1364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Incorrect 1 ms 1364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Incorrect 1 ms 1364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Incorrect 1 ms 1364 KB Output isn't correct
3 Halted 0 ms 0 KB -