| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1078587 | beaconmc | 로봇 대회 (IOI23_robot) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
ll prefrow[2001][2001];
ll prefcol[2001][2001];
ll grid[2001][2001];
bool checkrow(ll a, ll b, ll row){
if (a>b) swap(a,b);
return (prefrow[row][b] - prefrow[row][a] + grid[row][a] == 0);
}
bool checkcol(ll a, ll b, ll col){
if (a>b) swap(a,b);
return (prefcol[b][col] - prefcol[a][col] + grid[a][col] == 0);
}
vector<array<ll,2>> possible;
ll ans = 0;
ll cnt =0 ;
void idkman(vector<array<ll,2>>& sus, ll n, ll point){
if (sus.size()==n){
ll temp = 0;
for (auto&i : sus) temp += i[1] - i[0]+1;
array<ll,2> firsts,lasts;
for (auto&i : sus){
if (i != array<ll,2>{0,-1}){
firsts = i;
break;
}
}
for (auto&i : sus){
if (i != array<ll,2>{0,-1}){
lasts = i;
}
}
if ((firsts[0] <= lasts[0] && lasts[1] <= firsts[1]) || (lasts[0]<=firsts[0]&&firsts[1]<=lasts[1])){
ans = max(ans, temp);
}
return;
}
cnt++;
for (auto&i : possible){
if (i != array<ll,2>{0,-1} && prefrow[sus.size()][i[1]]-prefrow[sus.size()][i[0]]+grid[sus.size()][i[0]] != 0) continue;
if (sus.size() && i != array<ll,2>{0,-1}){
ll left = sus[sus.size()-1][0];
ll right = sus[sus.size()-1][1];
if (!(left==0 && right==-1) && !(left<=i[0] && i[1] <= right) && sus.size()>point){
continue;
}
if (!(left==0 && right==-1) && !(i[0]<=left && right <= i[1]) && sus.size()<=point){
continue;
}
}
if (sus.size() && i == array<ll,2>{0,-1} && sus[sus.size()-1] != i){
ll temp = 0;
for (auto&i : sus) temp += i[1] - i[0]+1;
array<ll,2> firsts,lasts;
for (auto&i : sus){
if (i != array<ll,2>{0,-1}){
firsts = i;
break;
}
}
for (auto&i : sus){
if (i != array<ll,2>{0,-1}){
lasts = i;
}
}
if ((firsts[0] <= lasts[0] && lasts[1] <= firsts[1]) || (lasts[0]<=firsts[0]&&firsts[1]<=lasts[1])){
ans = max(ans, temp);
}
continue;
}
sus.push_back(i);
idkman(sus, n, point);
sus.pop_back();
}
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
possible.clear();
ans = 0;
FOR(i,0,N){
FOR(j,0,N){
grid[i][j] = F[i][j];
}
}
FOR(i,0,N){
prefrow[i][0] = F[i][0];
FOR(j,1,N){
prefrow[i][j] = prefrow[i][j-1] + F[i][j];
}
}
FOR(j,0,N){
prefcol[0][j] = F[0][j];
FOR(i,1,N){
prefcol[i][j] = prefcol[i-1][j] + F[i][j];
}
}
FOR(i,0,N){
FOR(j,i,N){
possible.push_back({i,j});
}
}
possible.push_back({0,-1});
vector<array<ll,2>> lmao;
FOR(i,0,N){
idkman(lmao, N, i);
lmao.clear();
}
// vector<vector<ll>> special;
// FOR(i,a,b){
// FOR(j,c,d){
// temp -= grid[i][j];
// vector<vector<ll>> sus = {{i-1,j}, {i+1,j}, {i,j-1}, {i,j+1}};
// if (grid[i][j] != 1){
// bool flag = 0;
// for (auto&k : sus){
// if (0<=k[0] && k[0]<N && 0<=k[1] && k[1]<N){
// if (grid[k[0]][k[1]]==1) flag = 1;
// }
// }
// if (flag==1 || i==0 || i==N-1 || j==0 || j==N-1) special.push_back({i,j});
// }
// }
// }
// bool flag = false;
// for (auto&X : special){
// for (auto&Y : special){
// ll i = X[0], j = X[1], k = Y[0], l= Y[1];
// if (grid[i][j]==1 || grid[k][l] == 1) continue;
// bool check1 = (checkrow(l, j, i) && checkcol(k, i, l));
// bool check2 = (checkrow(l, j, k) && checkcol(k, i, j));
// if (!check1 && !check2) flag = true;
// }
// }
// if (!flag) ans = max(ans, temp);
return ans;
}