# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
752641 | 2023-06-03T11:05:24 Z | IBory | Seesaw (JOI22_seesaw) | C++14 | 711 ms | 1048576 KB |
#include <bits/stdc++.h> typedef long long ll; using namespace std; const int MAX = 200007; ll S[MAX], on[MAX]; int main() { ios::sync_with_stdio(0); cin.tie(0); int N; cin >> N; for (int i = 1; i <= N; ++i) { cin >> S[i]; S[i] += S[i - 1]; } int g = N / 2; vector<pair<double, int>> P; for (int d = 1; d <= N; ++d) { //if ((N - d) % 2 == 0) { // P.emplace_back((S[N - g] - S[N - g - d]) / (double)d, d); //} //else { // P.emplace_back((S[N - g] - S[N - g - d]) / (double)d, d); // P.emplace_back((S[N - g + 1] - S[N - g + 1 - d]) / (double)d, d); // g--; //} for (int i = d; i <= N; ++i) { P.emplace_back((S[i] - S[i - d]) / (double)d, d); } } sort(P.begin(), P.end()); double ans = 1e18; int cnt = 0, R = 0; on[P[0].second] = 1; for (int L = 0; L < P.size(); ++L) { while (R + 1 < P.size() && cnt != N - 1) { int t = P[++R].second; if (t != 1 && on[t - 1] && !on[t]) cnt++; if (t != N && on[t + 1] && !on[t]) cnt++; on[t]++; } if (cnt == N - 1) ans = min(ans, P[R].first - P[L].first); int t = P[L].second; on[t]--; if (t != 1 && on[t - 1] && !on[t]) cnt--; if (t != N && on[t + 1] && !on[t]) cnt--; } cout.precision(12); cout << fixed << ans; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 468 KB | Output is correct |
5 | Correct | 1 ms | 468 KB | Output is correct |
6 | Correct | 2 ms | 468 KB | Output is correct |
7 | Correct | 1 ms | 468 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 468 KB | Output is correct |
5 | Correct | 1 ms | 468 KB | Output is correct |
6 | Correct | 2 ms | 468 KB | Output is correct |
7 | Correct | 1 ms | 468 KB | Output is correct |
8 | Correct | 217 ms | 33340 KB | Output is correct |
9 | Correct | 240 ms | 33316 KB | Output is correct |
10 | Correct | 211 ms | 33320 KB | Output is correct |
11 | Correct | 213 ms | 33260 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 468 KB | Output is correct |
5 | Correct | 1 ms | 468 KB | Output is correct |
6 | Correct | 2 ms | 468 KB | Output is correct |
7 | Correct | 1 ms | 468 KB | Output is correct |
8 | Correct | 217 ms | 33340 KB | Output is correct |
9 | Correct | 240 ms | 33316 KB | Output is correct |
10 | Correct | 211 ms | 33320 KB | Output is correct |
11 | Correct | 213 ms | 33260 KB | Output is correct |
12 | Runtime error | 711 ms | 1048576 KB | Execution killed with signal 9 |
13 | Halted | 0 ms | 0 KB | - |