Submission #1215422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215422		brinton	Rectangles (IOI19_rect)	C++20	59 / 100	1472 ms	1114112 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"
using namespace std;

long long count_rectangles(vector<vector<int> > a) {
    int N = a.size(),M = a[0].size();
    if(N < 3 || M < 3) return 0LL;

    // vector<vector<vector<short>>> horivalid(N,vector<vector<short>>(M,vector<short>(M,0)));// i,l,r
    vector<vector<vector<short>>> vertvalid(M,vector<vector<short>>(N,vector<short>(N,0)));// j,l,r;


    for(int j = 0;j < M;j++){
        for(int l = 0;l+2 < N;l++){
            int cmax = a[l+1][j];    
            for(int r = l+2;r < N;r++){
                if(cmax < a[l][j] && cmax < a[r][j]){
                    vertvalid[j][l][r] = true;
                }
                cmax = max(cmax,a[r][j]);
                if(a[l][j] <= cmax) break;
            }
        }
    }


    for(int j = 1;j < M;j++){
        for(int l = 0;l < N;l++){
            for(int r = 0;r < N;r++){
                if(vertvalid[j][l][r]){
                    vertvalid[j][l][r] += vertvalid[j-1][l][r];
                }
            }
        }
    }


    long long ans = 0;
    vector<vector<short>> horivalid(M,vector<short>(M,0));
    for(int bottom = 1;bottom+1 < N;bottom++){
        vector<vector<short>> newHori(M,vector<short>(M,0));
        for(int l = 0;l+2 < M;l++){
            int cmax = a[bottom][l+1];    
            for(int r = l+2;r < M;r++){
                if(cmax < a[bottom][l] && cmax < a[bottom][r]){
                    newHori[l][r] = true;
                }
                cmax = max(cmax,a[bottom][r]);
                if(a[bottom][l] <= cmax) break;
            }
        }
        for(int l = 0;l < M;l++){
            for(int r = 0;r < M;r++){
                if(newHori[l][r]){
                    newHori[l][r] += horivalid[l][r];
                }
            }
        }
        swap(newHori,horivalid);
        for(int l = 0;l+2 < M;l++){
            for(int r = l+2;r < M;r++){
                int minTop = max(0,bottom-horivalid[l][r]);
                int cbottom = bottom+1;
                for(int ctop = minTop;ctop < bottom;ctop++){
                    // cout << l+1 << " " << r-1 << " " << ctop+1 << " " << cbottom-1 << endl;
                    if(vertvalid[r-1][ctop][cbottom] >= r-l-1) ans++;
                }
            }
        }
    }
    return ans;
}

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