제출 #252641

#제출 시각아이디문제언어결과실행 시간메모리
252641Dilshod_ImomovRectangles (IOI19_rect)C++17
10 / 100
5093 ms70268 KiB
# 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...