Submission #842043

#TimeUsernameProblemLanguageResultExecution timeMemory
842043allin27xSoccer Stadium (IOI23_soccer)C++17
1.50 / 100
249 ms63056 KiB
#include <bits/stdc++.h> using namespace std; int prx[2001][2001]; int pry[2001][2001]; int biggest_stadium(int n, vector<vector<int>> a){ for (int i=0; i<n; i++){ for (int j=0; j<n; j++){ prx[i+1][j+1] = prx[i][j+1] + a[i][j]; pry[i+1][j+1] = pry[i+1][j] + a[i][j]; } } vector<int> minx(n, n+1), maxx(n,0), miny(n, n+1), maxy(n, 0); int cnt = 0; for (int i=0; i<n; i++){ for (int j=0; j<n; j++){ cnt+=!a[i][j]; if (a[i][j]) continue; minx[i] = min(minx[i], j); maxx[i] = max(maxx[i], j); miny[j] = min(miny[j], i); maxy[j] = max(maxy[j], i); } } for (int i=0; i<n; i++){ if (minx[i]==n+1) continue; if (pry[i+1][maxx[i]+1] - pry[i+1][minx[i]] > 0) return 0; } for (int j=0; j<n; j++){ if (miny[j] ==n+1) continue; if (prx[maxy[j]+1][j+1] - prx[miny[j]][j+1] > 0) return 0; } for (int i=0; i<n; i++){ minx[i] = n+1; maxx[i] = -1; maxy[i] = -1; miny[i] = n+1; } for (int i=0; i<n; i++){ int st = 0; for (int j=0; j<n; j++){ if (a[i][j]){ if (!st) minx[i] = j; if (st && maxx[i] == -1) maxx[i] = j; } else st = 1; } } for (int j=0; j<n; j++){ int st = 0; for (int i=0; i<n; i++){ if (a[i][j]){ if (!st) miny[j] =i; if (st && maxy[j] == -1) maxy[j] = i; } else st = 1; } } for (int i=0; i<n; i++){ for (int j=0; j<n; j++){ if (a[i][j]) continue; for (auto [x,y]: vector<pair<int,int>> {{miny[j],minx[i]}, {miny[j],maxx[i]}, {maxy[j],maxx[i]}, {maxy[j], minx[i]} }){ if (x==-1 || x==n+1 || y==-1 || y==n+1) continue; if (!a[x][y]) return 0; } } } return cnt; }
#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...