oj.uz

Submission #700839

# Submission time Handle Problem Language Result Execution time Memory
700839 2023-02-19T09:04:01 Z m_fenais Seesaw (JOI22_seesaw) C++17
0 / 100
 2000 ms 748 KB 
#include <bits/stdc++.h>
#define endl '\n'
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int ll
#define all(vec) vec.begin(), vec.end()
typedef long long ll;
using namespace std;
const int N = 200 + 10, mod = 1e9 + 7;
int n;
double pref[N];
map<pair<int, int>, set<pair<double, double> > > mp;
void solve(int i, int j, int prev_i, int prev_j) {
    if(i > j) return;
    double a = double(double(pref[j] - pref[i-1])/double(j-i+1));
    for(auto it : mp[{prev_i, prev_j}]) {
        double b = min(it.first, a);
        double c = max(it.second, a);
        mp[{i, j}].insert({b, c});
    }
    solve(i, j - 1, i, j);
    solve(i + 1, j, i, j);
    return;
}
signed main()
{
    FAST;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> pref[i];
    for(int i = 2; i <= n; i++) pref[i] += pref[i-1];
    mp[{1, n}].insert({double(pref[n] / double(n)), double(pref[n] / double(n))});
    solve(1, n, 1, n);
    double ans = INT_MAX;
    for(int i = 1; i <= n; i++) {
        for(auto it : mp[{i, i}]) {
            ans = min(ans, double(abs(double(it.first) - double(it.second))));
        }
    }
    cout << fixed << setprecision(9) << ans << endl;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 2072 ms 748 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 2072 ms 748 KB Time limit exceeded
3 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 Execution timed out 2072 ms 748 KB Time limit exceeded
3 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 Execution timed out 2072 ms 748 KB Time limit exceeded
3 Halted 0 ms 0 KB -