Submission #880086

#TimeUsernameProblemLanguageResultExecution timeMemory
880086RaresFelixSoccer Stadium (IOI23_soccer)C++17
2 / 100
4561 ms436 KiB
#include "soccer.h" #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using ii = pair<int, int>; vector<ii> Sol; int sum(int lin, int l, int r, vector<vi> &SL) { if(!l) return SL[lin][r]; return SL[lin][r] - SL[lin][l - 1]; } bool ok(int l1, int r1, int l2, int r2) { if(l1 > l2) { swap(l1, l2); swap(r1, r2); } if(r2 <= r1) return 1; return l2 == l1; } int reg, nrsol; void gen(int n, int lin, vector<vi> &SL, int rec) { reg = max(reg, rec); // if(rec == 21) { // for(auto [a, b] : Sol) // cout << a << " " << b << "\n"; // cout << "\n\n"; // } ++nrsol; if(lin == n) return; for(int i = 0; i < n; ++i) { for(int j = i; j < n; ++j) { if(!sum(lin, i, j, SL)) { bool cont = 1; if(!Sol.empty()) { auto [st, dr] = Sol.back(); for(int i = Sol.size() - 1; i >= 0; --i) { if(Sol[i].first < st && i < st) { cont = 0; break; } if(Sol[i].second > dr && j > dr) { cont = 0; break; } st = max(st, Sol[i].first); dr = min(dr, Sol[i].second); } if(!cont) continue; } for(auto it : Sol) cont &= ok(it.first, it.second, i, j); if(cont) { Sol.push_back({i, j}); gen(n, lin + 1, SL, rec + j - i + 1); Sol.pop_back(); } } } } } int biggest_stadium(int n, std::vector<std::vector<int>> F) { vector<vi> SL(n, vi(n, 0)); int nrtree = 0; for(int i = 0; i < n; ++i) { SL[i][0] = F[i][0]; for(auto it : F[i]) nrtree += it; for(int j = 1; j < n; ++j) SL[i][j] = SL[i][j - 1] + F[i][j]; } if(!nrtree) return n * n; reg = 0; gen(n, 0, SL, 0); //cout << nrsol << " - \n"; return reg; }
#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...