Submission #1205395

#TimeUsernameProblemLanguageResultExecution timeMemory
1205395sula2Seesaw (JOI22_seesaw)C++20
0 / 100
0 ms396 KiB
#include <bits/stdc++.h> #define all(a) a.begin(), a.end() #define popcount(x) __builtin_popcountll(x) using namespace std; using namespace chrono; int a[100]; long double avg[100][100]; bool active[100][100], visited[100][100]; bool dfs(int l, int r) { if (!active[l][r] || visited[l][r]) return false; if (l == r) return true; visited[l][r] = true; return dfs(l+1, r) | dfs(l, r-1); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 0; i < n; cin >> a[i++]); // for (int i = 0; i < n; a[i++] = i); for (int l = 0; l < n; l++) { avg[l][l] = a[l]; for (int r = l+1; r < n; r++) { avg[l][r] = avg[l][r-1] + a[r]; } for (int r = l; r < n; r++) avg[l][r] /= r-l+1; } vector<tuple<int,int,double>> nodes; for (int l = 0; l < n; l++) { for (int r = l; r < n; r++) { nodes.emplace_back(l, r, avg[l][r]); } } sort(all(nodes), [&](tuple<int,int,double> a, tuple<int,int,double> b) { return get<2>(a) < get<2>(b); }); int r = 0; double ans = 1e9; for (int l = 0; l < nodes.size(); l++) { { // auto [x, y, z] = nodes[l]; // cout<<x<<' '<<y<<' '<<z<<'\n'; } while (r < nodes.size() && !dfs(0, n-1)) { auto [x, y, z] = nodes[r++]; active[x][y] = true; memset(visited, false, sizeof visited); } if (dfs(0, n-1)) { auto [b, c, d] = nodes[l]; auto [e, f, g] = nodes[r-1]; ans = min(ans, g - d); } auto [x, y, z] = nodes[l]; active[x][y] = false; } cout << fixed << setprecision(10) << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...