제출 #340432

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
340432		Marlov	Rectangles (IOI19_rect)	C++14	0 / 100	12 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<M-1;i++){
		for(int j=1;j<N-1;j++){
			int cm=0;
			for(int k=j;k<N-1;k++){
				cm=max(cm,a[k][i]);
				if(cm>a[j-1][i]&&cm<a[k+1][i]) rows[i][j][k]=true;
				else rows[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(cols[i+tr][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
*/

• 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