oj.uz

Submission #877816

# Submission time Handle Problem Language Result Execution time Memory
877816 2023-11-23T15:35:24 Z frostray8653 Seesaw (JOI22_seesaw) C++17
67 / 100
 2000 ms 5344 KB 
// #pragma GCC optimize("Ofast,unroll-loops,O3")
#include <bits/stdc++.h>
#define int long long
// #define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define IO ios::sync_with_stdio(0), cin.tie(0)
#define FOR(i, a, b) for (int i = a, I = b; i <= b; i++)
using namespace std;
void dbg() {;}
template<class T, class ...U>
void dbg(T a, U ...b) {cout << a << " "; dbg(b...);}
void ent() {cout << "\n";}

const int mod = 998244353;
// const int mod = 1e9 + 7;
// const int INF = 2e9;
const int INF = 1e18;

/// ------- Initialization End -------

const int N = 200005;
int a[N], pre[N];

double enumerate(int l, int r, double mn, double mx) {
    if (l == r)
        return mx - mn;
    double lres = (double)(pre[r] - pre[l]) / (r - l);
    if (lres <= mx)
        return enumerate(l + 1, r, mn, mx);
    double rres = (double)(pre[r - 1] - pre[l - 1]) / (r - l);
    if (rres >= mn)
        return enumerate(l, r - 1, mn, mx);
    return min(enumerate(l + 1, r, mn, lres), enumerate(l, r - 1, rres, mx));
}

signed main() {
    IO;
    
    int n;
    cin >> n;
    FOR(i, 1, n) cin >> a[i];
    double tot = 0;
    FOR(i, 1, n) tot += a[i];
    double ave = tot / n;
    FOR(i, 1, n) pre[i] = pre[i - 1] + a[i];
    double ans = enumerate(1, n, ave, ave);
    cout << fixed << setprecision(10) << ans << "\n";

    return 0;
}

Compilation message

seesaw.cpp: In function 'int main()':
seesaw.cpp:8:38: warning: unused variable 'I' [-Wunused-variable]
    8 | #define FOR(i, a, b) for (int i = a, I = b; i <= b; i++)
      |                                      ^
seesaw.cpp:42:5: note: in expansion of macro 'FOR'
   42 |     FOR(i, 1, n) cin >> a[i];
      |     ^~~
seesaw.cpp:8:38: warning: unused variable 'I' [-Wunused-variable]
    8 | #define FOR(i, a, b) for (int i = a, I = b; i <= b; i++)
      |                                      ^
seesaw.cpp:44:5: note: in expansion of macro 'FOR'
   44 |     FOR(i, 1, n) tot += a[i];
      |     ^~~
seesaw.cpp:8:38: warning: unused variable 'I' [-Wunused-variable]
    8 | #define FOR(i, a, b) for (int i = a, I = b; i <= b; i++)
      |                                      ^
seesaw.cpp:46:5: note: in expansion of macro 'FOR'
   46 |     FOR(i, 1, n) pre[i] = pre[i - 1] + a[i];
      |     ^~~

Subtask #1
1.0 / 1.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 689 ms 2648 KB Output is correct
9 Correct 4 ms 2392 KB Output is correct
10 Correct 5 ms 2396 KB Output is correct
11 Correct 272 ms 2532 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 689 ms 2648 KB Output is correct
9 Correct 4 ms 2392 KB Output is correct
10 Correct 5 ms 2396 KB Output is correct
11 Correct 272 ms 2532 KB Output is correct
12 Execution timed out 2004 ms 5344 KB Time limit exceeded
13 Halted 0 ms 0 KB -