Submission #826946

#	Time	Username	Problem	Language	Result	Execution time	Memory
826946		vjudge1	Rectangles (IOI19_rect)	C++17	37 / 100	5101 ms	37748 KiB

rect

#include<bits/stdc++.h>
#include "rect.h"

using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define ll long long
#define vout(v) for(int i=0; i<v.size(); i++) cout<<v[i]<<' ';
                                    
int a[3000][3000];
int gr[3000];

long long count_rectangles(vector<vector<int> > S){
	int n=S.size(), m=S[0].size();
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			a[i][j] = S[i-1][j-1];
		}
	}
	if(n <= 2 or m <= 2){
		return 0;
	}
	if(n <= 3){
		ll ans=0;
		for(int i=1; i<m-1; i++){
			int mx=a[2][i+1];
			int ok = (a[2][i+1] < a[1][i+1] and a[2][i+1] < a[3][i+1]);
			for(int j=i+2; j<=m; j++){
				
				if(min(a[2][i], a[2][j]) > mx and ok){
					ans++;
				}
				mx = max(mx, a[2][j]);
				ok = (ok and (a[2][j] < a[1][j] and a[2][j] < a[3][j]));
			}
		}
		return ans;
	}
	if(n <= 100){
		ll ans=0;
		
		
		for(int i=2; i<n; i++){
			for(int j=2; j<m; j++){
				for(int x=i; x<n; x++){
					int ok=1, dok=1; 
					for(int k=i; k<=x; k++){
						gr[k] = 0;
					}
					for(int y=j; y<m; y++){
						for(int k=i; k<=x; k++){
							if(a[k][y] >= a[i-1][y] or a[k][y] >= a[x + 1][y]){
								ok = 0;
								break;
							}
							
						}
						if(!ok) break;
						dok = 1;
						for(int k=i; k<=x; k++){
							gr[k] = max(gr[k], a[k][y]);
							if(gr[k] >= min(a[k][j-1], a[k][y+1])) dok = 0;                   
						}
						ans += dok;
					}
				}
			}
		}
		return ans;

	}
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:73:1: warning: control reaches end of non-void function [-Wreturn-type]
   73 | }
      | ^

• 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