Submission #340429

#	Time	Username	Problem	Language	Result	Execution time	Memory
340429		Marlov	Rectangles (IOI19_rect)	C++14	0 / 100	5061 ms	6508 KiB

rect

/*
Code by @marlov       
*/
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <utility>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <iterator>
#include <bitset>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

long long count_rectangles(vector< vector<int> > a){
	int N=a.size();
	int M=a[0].size();
	int result=0;

	bool cols[N][M][M];
	bool rows[M][N][N];
	for(int i=1;i<N-1;i++){
		for(int j=1;j<M-1;j++){
			int cm=0;
			for(int k=j;k<M-1;k++){
				cm=max(cm,a[i][k]);
				if(cm>a[i][j-1]&&cm<a[i][k+1]) cols[i][j][k]=true;
				else cols[i][j][k]=false;
			}
		}
	}
	for(int i=1;i<N-1;i++){
		for(int j=1;j<M-1;j++){
			for(int k=j;k<M-1;k++){
				int tr=0;
				while(rows[i][j][k]){
					bool pc=true;
					for(int x=j;x<=k;x++){
						if(!rows[x][i][i+tr]) pc=false;
					}
					if(pc) result++;
					tr++;
				}
			}
		}
	}
	
return result;

}
/*
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cout<<count_rectangles( {{4, 8, 7, 5, 6}},{7, 4, 10, 3, 5},{9, 7, 20, 14, 2},{9, 14, 7, 3, 6},{5, 7, 5, 2, 7},{4, 5, 13, 5, 6}} );
    return 0;
}
*/

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1,n=0?)
	* do smth instead of nothing and stay organized
*/

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:31:7: warning: variable 'cols' set but not used [-Wunused-but-set-variable]
   31 |  bool cols[N][M][M];
      |       ^~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28