Submission #154134

#	Time	Username	Problem	Language	Result	Execution time	Memory
154134		79brue	Rectangles (IOI19_rect)	C++14	15 / 100	5030 ms	41312 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"

using namespace std;
typedef long long ll;

int n, m;
int board[2502][2502];
int maxVal1[82][82][82]; /// ----
int maxVal2[82][82][82]; /// ||||

ll count_rectangles(vector<vector<int> > _var) {
    n = (int)_var.size();
    m = (int)_var[0].size();
    ll ans = 0;
    bool pos;

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            board[i][j] = _var[i-1][j-1];
        }
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            for(int k=j; k<=m; k++){
                for(int l=j; l<=k; l++){
                    maxVal1[i][j][k] = max(maxVal1[i][j][k], board[i][l]);
                }
            }
        }
    }

    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            for(int k=j; k<=n; k++){
                for(int l=j; l<=k; l++){
                    maxVal2[i][j][k] = max(maxVal2[i][j][k], board[l][i]);
                }
            }
        }
    }

    for(int i=2; i<n; i++){
        for(int j=2; j<m; j++){
            for(int k=i; k<n; k++){
                for(int l=j; l<m; l++){
                    pos = 1;
                    for(int x=i; x<=k; x++){
                        if(maxVal1[x][j][l] >= min(board[x][j-1], board[x][l+1])){
                            pos = 0;
                            break;
                        }
                    }
                    for(int y=j; y<=l; y++){
                        if(maxVal2[y][i][k] >= min(board[i-1][y], board[k+1][y])){
                            pos = 0;
                            break;
                        }
                    }
                    if(pos) ans++;
                }
            }
        }
    }

    return ans;
}

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