Submission #723035

#	Time	Username	Problem	Language	Result	Execution time	Memory
723035		victor_gao	Rectangles (IOI19_rect)	C++17	27 / 100	5059 ms	51080 KiB

rect

#pragma GCC optimize("Ofast,unroll-loops")
#include "rect.h"
#include <bits/stdc++.h>
#define ll long long
#define N 805
using namespace std;
int arr[N][N],n,m,mx[N];

long long count_rectangles(std::vector<std::vector<int> > a) {
	n=a.size(); m=a[0].size();
	ll ans=0;
	for (int i=0;i<n;i++){
		for (int j=0;j<m;j++)
			arr[i][j]=a[i][j];
	}
	for (int i=1;i<n-1;i++){
        for (int j=1;j<m-1;j++){
            for (int k=j;k<m-1;k++){
                for (int l=j;l<=k;l++)
                    mx[l]=0;
                for (int l=i;l<n-1;l++){
                    int lmx=0,add=1;
                    for (int h=j;h<=k;h++){
                        lmx=max(lmx,arr[l][h]);
                        mx[h]=max(mx[h],arr[l][h]);
                        if (mx[h]>=arr[i-1][h]||mx[h]>=arr[l+1][h])
                            add=0;
                    }
                    if (lmx>=arr[l][j-1]||lmx>=arr[l][k+1])
                        break;
                 //   cout<<"add "<<i<<"~"<<l<<" , "<<j<<"~"<<k<<" : "<<add<<'\n';
                    ans+=add;
                }
            }
        }
    }
	return ans;
}
/*
4 4
3 3 3 3
3 1 2 3
4 2 3 4
4 4 4 4
*/

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