Submission #298422

#	Time	Username	Problem	Language	Result	Execution time	Memory
298422		Rayaabualjamal	Rectangles (IOI19_rect)	C++14	37 / 100	5098 ms	34040 KiB

rect

#include "rect.h"
#include <cassert>
#include <iostream> 
#include <set> 
#include <queue> 
#include <stack> 
#include <iterator>
#include <cmath>
#include <algorithm>
#include <vector> 
#include <map> 
#include <cstdio>
#define rep(i,a,b) for(int i = a; i<b; i++)
#define per(i,a,b) for(int i = a; i>=b; i--)
#define pb push_back
#define se second
using namespace std;
long long count_rectangles(std::vector<std::vector<int> > a) {
	int n = a.size()-1;
	int m = a[0].size()-1;
	vector < vector <int> > no(n+1, vector <int> (m+1,0));
	rep(i,0,n){
		int maxi = 0;
		rep(j,0,m){
			if(maxi<=a[i][j]){
				no[i][j]=1;
			}
			maxi = max(maxi, a[i][j]);
		}
	}
	per(i,n,0){
		int maxi = 0;
		per(j,m,0){
			if(maxi<=a[i][j]){
				no[i][j]=1;
			}
			maxi = max(maxi, a[i][j]);
		}
	}
	per(j,m,0){
		int maxi = 0;
		per(i,n,0){
			if(maxi<=a[i][j]){
				no[i][j]=1;
			}
			maxi = max(maxi, a[i][j]);
		}
	}
	rep(j,0,m){
		int maxi = 0;
		rep(i,0,n){
			if(maxi<=a[i][j]){
				no[i][j]=1;
			}
			maxi = max(maxi, a[i][j]);
		}
	}
	long long ans = 0;
	rep(i,1,n){
		rep(j,1,m){
			if(no[i][j])continue;
			int mini = m, minni = n;
			rep(ii,i,n){
				//if(ii>minni)break;
				rep(jj,j,m){
					if(jj>mini)break;
					if(no[ii][jj]){
						mini = min(mini,jj);
						minni = min(minni, ii);
						break;
					}
					bool f = 1;
					rep(k,i,ii+1){
						rep(l,j,jj+1){
							if(a[k][l]>=a[k][j-1]||a[k][l]>=a[k][jj+1]||a[k][l]>=a[i-1][l]||a[k][l]>=a[ii+1][l]){
								f = 0;
								break;
							}
						}
						if(!f)break;
					}
					if(f)ans++;
					//cout << i << " " << j << "   " << ii << " " << jj << endl;
				}
			}
		}
	}
	return ans;
}

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