# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1055513 | juliany2 | Seesaw (JOI22_seesaw) | C++17 | 53 ms | 13776 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
// path from (1, n) to any (i, i)
// as long as all diags have at least one valid theres always a valid path
// can connect any two of these points with a right/down path, which is monotic increasing
int main() {
cin.tie(0)->sync_with_stdio(false);
int n;
cin >> n;
vector<ll> a(n + 1), pref(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
pref[i] = pref[i - 1] + a[i];
}
double avg = (double) pref[n] / n;
vector<pair<double, int>> b;
b.push_back({avg, n});
for (int len = 1; len < n; len++) {
int lo = len, hi = n;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if ((double) (pref[mid] - pref[mid - len]) / len < avg)
lo = mid;
else
hi = mid - 1;
}
b.push_back({(double) (pref[lo] - pref[lo - len]) / len, len});
b.push_back({(double) (pref[lo + 1] - pref[lo + 1 - len]) / len, len});
}
sort(all(b));
vector<int> cnt(n + 1);
int valid = 0;
double ans = 1e18;
int r = -1;
for (int l = 0; l < b.size(); l++) {
while (r + 1 < b.size() && valid < n) {
r++;
if (!cnt[b[r].second]++)
valid++;
}
if (valid == n)
ans = min(ans, b[r].first - b[l].first);
if (!--cnt[b[l].second])
valid--;
}
cout << fixed << setprecision(15) << ans << '\n';
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |