| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 845798 | Sorting | Soccer Stadium (IOI23_soccer) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 500 + 3;
bool f[N][N];
int prefix[N][N];
int p2[N][N][N], prv[N][N][N], nxt[N][N][N];
int n;
pair<int, bool> dp[N][N][N];
int get_sum(int i, int l, int r){
if(l == 0)
return prefix[i][r];
return prefix[i][r] - prefix[i][l - 1];
}
bool bad(int l1, int r1, int l2, int r2){
if(l1 <= l2 && r2 <= r1)
return false;
if(l2 <= l1 && r1 <= r2)
return false;
return true;
}
pair<int, int> extend(int i, int j, int l, int r){
assert(prv[l][r][i] == prv[l][r][j]);
assert(nxt[l][r][i] == nxt[l][r][j]);
return {prv[l][r][i], nxt[l][r][j]};
}
int solve(int i, int j, int l, int r){
auto &[ans, solved] = dp[i][l][r];
if(solved)
return ans;
ans = 0;
solved = true;
if(l != r){
vector<pair<int, int>> v{{l + 1, r}, {l, r - 1}};
for(auto [l2, r2]: v){
auto [i2, j2] = extend(i, j, l2, r2);
int cand = (i - i2 + j2 - j) * (r2 - l2 + 1);
cand += solve(i2, j2, l2, r2);
ans = max(ans, cand);
}
}
return ans;
}
int biggest_stadium(int _N, std::vector<std::vector<int>> F){
n = _N;
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
f[i][j] = F[i][j];
for(int i = 0; i < n; ++i){
prefix[i][0] = f[i][0];
for(int j = 1; j < n; ++j)
prefix[i][j] = prefix[i][j - 1] + f[i][j];
}
for(int l = 0; l < n; ++l){
for(int r = l; r < n; ++r){
for(int i = 0; i < n; ++i){
p2[l][r][i] = get_sum(i, l, r);
}
}
}
for(int l = 0; l < n; ++l){
for(int r = l; r < n; ++r){
int x = 0;
for(int i = 0; i < n; ++i){
if(p2[l][r][i]){
x = i + 1;
}
else{
prv[l][r][i] = x;
}
}
x = n - 1;
for(int i = n - 1; i >= 0; --i){
if(p2[l][r][i]){
x = i - 1;
}
else{
nxt[l][r][i] = x;
}
}
}
}
int ans = 0;
for(int i = 0; i < n; ++i){
for(int l = 0; l < n; ++l){
for(int r = l; r < n; ++r){
if(f[i][r])
break;
auto [l2, r2] = extend(i, i, l, r);
ans = max(ans, solve(l2, r2, l, r) + (r - l + 1) * (r2 - l2 + 1));
}
}
}
return ans;
}
/*
3
1 1 1
1 1 1
1 1 1
*/