Submission #1229460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229460		Gray	Rectangles (IOI19_rect)	C++20	49 / 100	1639 ms	1025448 KiB

rect

#include <cstring>
#pragma GCC optimize("Ofast,unroll-loops")
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ff first
#define ss second

bool cols[699][699][699];
short int upw[699][699][699];

long long count_rectangles(vector<vector<int>> a) {
    memset(cols, 0, sizeof cols);
    memset(upw, 0, sizeof upw);
    int n=a.size(), m=a[0].size();
    int cmx, j, up, down, i, l, r;

    for (i=1; i<n-1; i++){
        for (l=1; l<m-1; l++){
            cmx=a[i][l];
            for (r=l; r<m-1; r++){
                cmx=max(cmx, a[i][r]);
                if (cmx<a[i][l-1] and cmx<a[i][r+1]){
                    cols[i][l][r]=1;
                }
            }
        }
    }
    for (i=1; i<n-1; i++){
        for (l=1; l<m-1; l++){
            for (r=l; r<m-1; r++){
                upw[i][l][r]=(cols[i][l][r]?upw[i-1][l][r]+1:0);
            }
        }
    }

    for (j=1; j<m-1; j++){
        for (up=1; up<n-1; up++){
            cmx=a[up][j];
            for (down=up; down<n-1; down++){
                cmx=max(cmx, a[down][j]);
                if (cmx<a[up-1][j] and cmx<a[down+1][j]){
                    cols[j][up][down]=1;
                }else cols[j][up][down]=0;
            }
        }
    }
    long long cnt=0;
    for (up=1; up<n-1; up++){
        for (down=up; down<n-1; down++){
            for (r=1; r<m-1; r++){
                for (l=r; l>=1; l--){
                    if (!cols[l][up][down]){
                        break;
                    }
                    if (upw[down][l][r]>=(down-up+1)) {
                        cnt++;
                    }
                }
            }
        }
    }
	return cnt;
}

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