Submission #1203851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203851		Aviansh	Rectangles (IOI19_rect)	C++20	37 / 100	5092 ms	22852 KiB

rect

#include "rect.h"

#include <bits/stdc++.h>

using namespace std;

long long count_rectangles(vector<vector<int>> a) {
    int n=a.size();
    int m=a[0].size();
    if(n<3||m<3)
        return 0;
    long long ans = 0;
    for(int i = 1;i<n-1;i++){
        for(int j = 1;j<m-1;j++){
            //(i,j) is starting point.
            int maxima[m];
            fill(maxima,maxima+m,0);
            bool valj[m];
            fill(valj,valj+m,1);
            for(int eni = i;eni<n-1;eni++){
                bool val = 1;
                int mx = 0;
                for(int enj = j;enj<m-1;enj++){
                    maxima[enj]=max(maxima[enj],a[eni][enj]);
                    mx=max(mx,a[eni][enj]);
                    //col maxima set
                    if(mx>=a[eni][enj+1]||mx>=a[eni][j-1]){
                        //bad j now
                        valj[enj]=0;
                    }
                    if(maxima[enj]<a[eni+1][enj]&&maxima[enj]<a[i-1][enj]){
                        //this column is fine.
                        if(val){
                            //prev cols also fine
                            if(valj[enj]){
                                //this j is good
                                ans++;
                            }
                        }
                    }
                    else{
                        //bad column subsequent cols also bad
                        val=0;
                    }
                }
            }
        }
    }
    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