이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
# include <bits/stdc++.h>
# include "rect.h"
# define ll long long
using namespace std;
const int N = 2507;
// bool dp[N][N][N]; // dp[i][j][i1] = 0/1; 1-> can create a rect starting from i,j ending at i1, j
ll sum[N][N];
long long count_rectangles(vector<vector<int> > a) {
int n = a.size(), m = a[0].size(), ans = 0, mx = 0;
for ( int i = 1; i <= n; i++ ) {
for ( int j = 1; j <= m; j++ ) {
mx = max( mx, a[i - 1][j - 1] );
sum[i][j] = a[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
}
if ( mx <= 1 ) {
vector < int > row[n + 1], col[m + 1];
for ( int i = 0; i < n - 1; i++ ) {
for ( int j = 0; j < m - 1; j++ ) {
if ( a[i][j] ) {
row[i].push_back( j + 1 );
col[j].push_back( i + 1 );
}
else {
if ( row[i].empty() || col[j].empty() ) {
continue;
}
int y = row[i].back(), x = col[j].back();
i++;
j++;
int s = ((i + 1) - x - 1) * 2;
s += ((j + 1) - y - 1) * 2;
s += a[x - 1][y - 1] + a[i][j] + a[x - 1][j] + a[i][y - 1];
if ( sum[i + 1][j + 1] - sum[x - 1][j + 1] - sum[i + 1][y - 1] + sum[x - 1][y - 1] == s ) {
// cout << x << ' ' << y << ' ' << i + 1 << ' ' << j + 1 << ' ' << s << '\n';
ans++;
}
i--;
j--;
}
}
}
return ans;
}
for ( int i = 1; i < n - 1; i++ ) {
for ( int j = 1; j < m - 1; j++ ) {
for ( int i1 = i; i1 < n - 1; i1++ ) {
for ( int j1 = j; j1 < m - 1; j1++ ) {
int ok = 1;
for ( int x = i; x <= i1; x++ ) {
for ( int y = j; y <= j1; y++ ) {
int A = a[i - 1][y], B = a[i1 + 1][y];
int C = a[x][j - 1], D = a[x][j1 + 1];
int z = a[x][y];
if ( z >= A || z >= B || z >= C || z >= D ) {
ok = 0;
break;
}
}
if ( !ok ) {
break;
}
}
ans += ok;
}
}
}
}
return ans;
}
/*
int32_t main() {
int n, m;
cin >> n >> m;
vector < vector < int > > a;
for ( int i = 0; i < n; i++ ) {
vector < int > vc;
for ( int j = 0; j < m; j++ ) {
int x;
cin >> x;
vc.push_back( x );
}
a.push_back( vc );
}
cout << count_rectangles(a);
}
/*
6 5
0 1 1 1 0
1 0 0 0 1
1 0 0 0 1
0 1 1 1 1
0 1 0 1 0
0 0 1 0 0
*/
컴파일 시 표준 에러 (stderr) 메시지
rect.cpp:90:1: warning: "/*" within comment [-Wcomment]
/*
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |