oj.uz

Submission #877821

# Submission time Handle Problem Language Result Execution time Memory
877821 2023-11-23T15:53:11 Z frostray8653 Seesaw (JOI22_seesaw) C++17
34 / 100
 2000 ms 348 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 = 2005;
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) { /// 取左邊的
        int ql = l + 1, qr = r;
        while (ql + 1 < qr) {
            int mid = (ql + qr) >> 1;
            if ((double)(pre[r] - pre[mid - 1]) / (r - mid + 1) <= mx)
                ql = mid;
            else
                qr = mid;
        }
        return enumerate(ql, r, mn, mx);
    }
    double rres = (double)(pre[r - 1] - pre[l - 1]) / (r - l);
    if (rres >= mn) { /// 取右邊的
        int ql = l, qr = r - 1;
        while (ql + 1 < qr) {
            int mid = (ql + qr) >> 1;
            if ((double)(pre[mid] - pre[l - 1]) / (mid - l + 1) >= mn)
                qr = mid;
            else
                ql = mid;
        }
        return enumerate(l, qr, 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:60:5: note: in expansion of macro 'FOR'
   60 |     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:62:5: note: in expansion of macro 'FOR'
   62 |     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:64:5: note: in expansion of macro 'FOR'
   64 |     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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct

Subtask #2
33.0 / 33.0

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

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Execution timed out 2051 ms 348 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Execution timed out 2051 ms 348 KB Time limit exceeded
9 Halted 0 ms 0 KB -