| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 963372 | tutis | 축구 경기장 (IOI23_soccer) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int biggest_stadium(int N, std::vector<std::vector<int>> C) {
vector<vector<int>> S(N);
auto fS = [&](int x, int y) {
if (x < 0 || y < 0) {
return 0;
}
return S[x][y];
};
auto sm = [&](int x1, int x2, int y1, int y2) -> int {
return fS(x2, y2) - fS(x1 - 1, y2) - fS(x2, y1 - 1) + fS(x1 - 1, y1 - 1);
};
for (int i = 0; i < N; i++) {
S[i] = vector<int>(N);
for (int j = 0; j < N; j++) {
S[i][j] = C[i][j];
S[i][j] += fS(i - 1, j) + fS(i, j - 1) - fS(i - 1, j - 1);
}
}
int best = 0;
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++) {
if (C[x][y] == 1) {
continue;
}
int x0 = x;
int x1 = x;
int y0 = y;
int y1 = y;
while (x0 - 1 >= 0 && C[x0 - 1][y] == 0) {
x0--;
}
while (x1 + 1 < N && C[x1 + 1][y] == 0) {
x1++;
}
while (y0 - 1 >= 0 && C[x][y0 - 1] == 0) {
y0--;
}
while (y1 + 1 < N && C[x][y1 + 1] == 0) {
y1++;
}
int p = 0;
int mx = y1;
int mn = y0;
for (int i = x; i <= x1; i++) {
while (sm(i, i, y, mx) != 0) {
mx--;
}
while (sm(i, i, mn, y) != 0) {
mn++;
}
p += mx - mn + 1;
// cout<<i<<" "<<mn<<" "<<mx<<endl;
}
mx = y1;
mn = y0;
for (int i = x - 1; i >= x0; i--) {
while (sm(i, i, y, mx) != 0) {
mx--;
}
while (sm(i, i, mn, y) != 0) {
mn++;
}
p += mx - mn + 1;
// cout<<i<<" "<<mn<<" "<<mx<<endl;
}
// cout<<endl;
best = max(best, p);
}
}
return best;
}
int main() {
std::cout << biggest_stadium(3, {{1, 0, 0},
{0, 0, 1},
{1, 0, 1}}) << std::endl;
return 0;
}