Submission #427060

#	Time	Username	Problem	Language	Result	Execution time	Memory
427060		Belgutei	Rectangles (IOI19_rect)	C++17	8 / 100	496 ms	45936 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
 
int ans;
 
long long count_rectangles(std::vector<std::vector<int> > v) {
	int n=v.size();
	int m=v[0].size();
	for(int i=1; i<n-1; i++){
		for(int j=1; j<m-1; j++){
			// starting node
			int a[40][40],b[40][30];
			for(int x=0; x<=30; x++){
				for(int y=0; y<=30; y++){
					a[x][y]=0;
					b[x][y]=0;
				}
			}
			// a[x][y]
			for(int x=i; x<n-1; x++){
				int cnt1=0;
				for(int y=j; y<m-1; y++){
					int cnt=0;
					for(int k=x-1; k>=i; k--){
						if(a[k][y]<v[k][y+1] && a[k][y]<v[k][j-1]) cnt++;
					}
					if(y-1>=j) a[x][y]=max(v[x][y],a[x][y-1]);
					else a[x][y]=v[x][y];
					if(a[x][y]<v[x][j-1] && a[x][y]<v[x][y+1] ) cnt++;
					b[x][y]=max(v[x][y],b[x-1][y]);
					if(b[x][y]<v[x+1][y] && b[x][y]<v[i-1][y]) cnt1++;
					if(cnt+cnt1==x-i+1+y-j+1) {
						ans++;
					}
				}
			}
		}
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:24:13: warning: iteration 30 invokes undefined behavior [-Waggressive-loop-optimizations]
   24 |      b[x][y]=0;
      |      ~~~~~~~^~
rect.cpp:22:19: note: within this loop
   22 |     for(int y=0; y<=30; y++){
      |                  ~^~~~

• Subtask 1: 8 / 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