| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 419042 | JediMaster11 | Split the Attractions (IOI19_split) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vint vector<int>
#define vll vector<long long>
#define fo(a, b, c) for (int a = b; a < (int)c; a++)
#define rfo(a, b, c) for (int a = b - 1; a >= (int)c; a--)
#define print(x) cout << x << "\n"
// ll smalln(vector<vint> grid){
// int n = grid.size();
// int m = grid[0].size();
// ll count=0;
// bool work=true;
// int maxEdge = max(grid[1][0], grid[1][m-1]);
// //subtask 5
// fo(i,1,m-1){
// fo(j,i,m-1){
// work=true;
// fo(x,i,j+1){
// int val = grid[1][x];
// if(val >= grid[1][i-1] || val >= grid[0][x] || val >= grid[2][x] || val >= grid[1][j+1])
// {
// work=false;
// break;
// }
// }
// if(work){
// count++;
// }
// }
// }
// return count;
// }
ll count_rectangles(vector<vint> grid)
{
int n = grid.size();
int m = grid[0].size();
if(n <=2 || m <= 2){
return 0;
}
ll count = 0;
// if(n==3){
// return smalln(grid);
// }
bool done[n][m]; // ignore when done=true
fo(i,0,n){
fo(j,0,m){
done[i][j]=false;
}
}
int max;
// if its smaller than a side piece, ignore it in bool array
// tallest in any row or grid can be ignored
fo(i, 0, n)
{
max = -1;
fo(j, 0, m)
{
if (grid[i][j] > max)
{
max = grid[i][j];
}
}
fo(j, 0, m)
{
if (grid[i][j] == max)
{
done[i][j] = true;
}
}
if (grid[i][0] <= grid[i][1])
{
done[i][1] = true;
}
if (grid[i][m - 1] <= grid[i][m - 2])
{
done[i][m - 2] = true;
}
}
fo(j, 0, m)
{
max = -1;
// pos = -1;
fo(i, 0, n)
{
if (grid[i][j] > max)
{
max = grid[i][j];
// pos = i;
}
}
fo(i, 0, n)
{
if (grid[i][j] == max)
{
done[i][j] = true;
}
}
if (grid[0][j] <= grid[1][j])
{
done[1][j] = true;
}
if (grid[n - 1][j] <= grid[n - 2][j])
{
done[n - 2][j] = true;
}
}
// vector<pair<int,int>> works;
// fo(i,1,n-1){
// fo(j,1,m-1){
// if(!done[i][j]){
// int val = grid[i][j];
// if(val < grid[i][j+1] && val < grid[i][j-1] && val < grid[i+1][j] && val < grid[i-1][j]){
// works.push_back({i,j});
// }
// }
// }
// }
// count = works.size();
fo(i1, 1, n - 1)
{
fo(j1, 1, m - 1)
{
fo(i2, i1, n - 1)
{
fo(j2, j1, m - 1)
{
bool works = true;
fo(y, i1, i2 + 1)
{
fo(x, j1, j2 + 1)
{
int val = grid[y][x];
if (done[y][x])
{
works = false;
}
if (val >= grid[y][j1 - 1] || val >= grid[y][j2 + 1] || val >= grid[i1 - 1][x] || val >= grid[i2 + 1][x])
{
works = false;
}
if (!works)
{
x = j2+1;
y = i2+1;
break;
}
}
}
if (works)
{
count++;
// print(i1 << " -> " << i2);
// print(j1 << " -> " << j2);
// print("");
}
}
}
}
}
return count;
}