Submission #1082084

#TimeUsernameProblemLanguageResultExecution timeMemory
1082084ArthuroWichSoccer Stadium (IOI23_soccer)C++17
6 / 100
196 ms32596 KiB
#include "soccer.h" #include<bits/stdc++.h> using namespace std; int n, ans = 0; vector<vector<pair<int, int>>> segs; map<tuple<int, int, int>, int> dp1, dp2; int solveup(int i, int l, int r) { if (dp1.find({i, l, r}) != dp1.end()) { return dp1[{i, l, r}]; } if (i == 0) { return r-l+1; } int v = 0; for (auto [x, y] : segs[i-1]) { if (r < x || y < l) { continue; } v = max(v, solveup(i-1, max(l, x), min(r, y))); } dp1[{i, l, r}] = v+(r-l+1); return v+(r-l+1); } int solvedown(int i, int l, int r) { if (dp2.find({i, l, r}) != dp2.end()) { return dp2[{i, l, r}]; } if (i == n-1) { return r-l+1; } int v = 0; for (auto [x, y] : segs[i+1]) { if (r < x || y < l) { continue; } v = max(v, solvedown(i+1, max(l, x), min(r, y))); } dp2[{i, l, r}] = v+(r-l+1); return v+(r-l+1); } int biggest_stadium(int N, vector<vector<int>> f) { n = N; segs.resize(n); for (int i = 0; i < n; i++) { int l = -1, r = -1; for (int j = 0; j < n; j++) { if (f[i][j] == 0) { if (l == -1) { l = j; } r = j; } else { if (l != -1) { segs[i].push_back({l, r}); } l = -1; } } if (l != -1) { segs[i].push_back({l, r}); } } for (int i = 0; i < n; i++) { for (auto [x, y] : segs[i]) { ans = max(ans, solveup(i, x, y)+solvedown(i, x, y)-(y-x+1)); } } return 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...