Submission #1021077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021077		Malix	Rectangles (IOI19_rect)	C++14	37 / 100	5048 ms	84984 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))

ll INF=1e18+10;
int inf=1e9+10;
ll M=1e9+7;

long long count_rectangles(std::vector<std::vector<int> > a) {
	int n=a.size();
	int m=a[0].size();
	vii b(n,vi(m,0)),c(n,vi(m,0));
	ll ans=0;
	REP(i,1,n-1)REP(j,1,m-1){
		vii top(n,vi(m,0)),left(n,vi(m,0)),d(n,vi(m,0));
		REP(x,i,n-1)REP(y,j,m-1){
			top[x][y]=max(top[x-1][y],a[x][y]);
			left[x][y]=max(left[x][y-1],a[x][y]);
		}
		REP(y,j,m-1)d[i-1][y]=1;
		REP(x,i,n-1)REP(y,j,m-1)if(left[x][y]<a[x][j-1]&&left[x][y]<a[x][y+1]&&d[x-1][y])d[x][y]=1;
		REP(x,i,n-1){
			REP(y,j,m-1){
				if(top[x][y]>=a[i-1][y]||top[x][y]>=a[x+1][y])break;
				if(d[x][y]){
					ans++;//cerr<<i<<" "<<j<<" "<<x<<" "<<y<<"\n";
				}
			}
		}
		// if(i==n-2&&j==m-2){cout<<"\n";
		// 	REP(x,i,n-1){
		// 		REP(y,j,m-1)cout<<d[x][y]<<" ";
		// 	cout<<"\n";
		// 	}
		// }
	}
	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