Submission #429418

#	Time	Username	Problem	Language	Result	Execution time	Memory
429418		APROHACK	Rectangles (IOI19_rect)	C++14	10 / 100	5 ms	384 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
long long n, m;
long long count_rectangles(std::vector<std::vector<int> > a) {
	n=a.size(), m=a[0].size();
	//cout<<n<<m<<endl;
	long long rta = 0;
	if(n==3){
		for(int i = 1 ; i < m-1 ; i++){
			int mx=0;
			for(int j = i ; j< m-1 ; j++){
				mx=max(a[1][j], mx);
				if(a[1][j]>=a[0][j]||a[1][j]>=a[2][j]||a[1][j]>=a[1][i-1])break;
				if(mx<a[1][j+1])rta++;
			}

		}
	}else{
		bool flag;
		int ps, ps2, limx, limy;
		for(int i = 1 ; i < n-1 ; i++ ){
			for(int j = 1 ; j < m-1 ; j++){
				flag= false;
				if(a[i][j]==0&&a[i-1][j]==1&&a[i][j-1]==1){
					int it = i+1;
					while(it<n-1 && a[it][j]==0){
						if(a[it][j-1]!=1){
							flag = true;
							break;
						}
						//cout<<it<<" "<<j<<endl;
						it++;
					}
					if(flag)continue;
					it--;
					if(a[it+1][j]!=1)continue;
					
					ps=it;
					it=j+1;
					while(it<m-1 && a[ps][it]==0){
						if(a[ps+1][it]!=1){
							flag = true;
							break;
						}
						//cout<<i<<" "<<it<<endl;
						it++;
					}
					if(flag)continue;
					it--;
					if(a[i][it+1]!=1)continue;
					ps2=it;
					limy=ps;
					limx=ps2;
					it=ps-1;
					while(it>0 && a[it][ps2]==0){
						if(a[it][ps2+1]!=1){
							flag = true;
							break;
						}
						//cout<<it<<" "<<ps2<<endl;
						it--;
					}
					if(flag)continue;
					it++;
					if(a[it-1][ps2]!=1)continue;
					ps=it;
					it=ps2-1;
					while(it>0 && a[ps][it]==0){
						if(a[ps-1][it]!=1){
							flag = true;
							break;
						}
						//cout<<ps<<" "<<it<<endl;
						it--;
					}
					if(flag)continue;
					it++;
					if(a[ps][it-1]!=1||ps!=i||it!=j)continue;
					for(int y = i ; y <= limy ; y++){
						for(int x = j ; x<=limx ; x++){
							//recorrido[y][x]=true;
							if(a[y][x]==1){
								flag=true;
								break;
							}
						}
						if(flag)break;
					}
					if(!flag){
						rta++;
						//cout<<i<<" "<<j<<endl;
					}
				}
			}
		}
	}
	return rta;
}

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