Submission #579956

#	Time	Username	Problem	Language	Result	Execution time	Memory
579956		SlavicG	Rectangles (IOI19_rect)	C++17	37 / 100	1349 ms	1048576 KiB

rect

#include "rect.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
long long count_rectangles(std::vector<std::vector<int>> a) {
    ll ans = 0;
    int n = a.size(), m = a[0].size();
    vector<vector<vector<int>>> mx(n, vector<vector<int>>(m, vector<int>(m, INT_MIN)));

    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            int mxx = INT_MIN;
            for(int k = j; k < m; ++k) {
                mxx = max(mxx, a[i][k]);
                mx[i][j][k] = mxx;
            }
        }
    }
    vector<vector<vector<int>>> col(n, vector<vector<int>>(n, vector<int>(m, 0)));

    for(int i = 1; i + 1 < n; ++i) {
        for(int j = 0; j < m; ++j) {
            int curmax = a[i][j];
            for(int k = i; k + 1 < n; ++k) {
                curmax = max(curmax, a[k][j]);
                if(curmax < a[i - 1][j] && curmax < a[k + 1][j]) {
                    ++col[i][k][j];
                }
            }
        }
    }
    for(int i = 1; i + 1 < n; ++i) {
        for(int k = i; k + 1 < n; ++k) {
            for(int j = 1; j < m; ++j) {
                col[i][k][j] += col[i][k][j - 1];
            }
        }
    }
    for(int i = 1; i + 1 < n; ++i) {
        for(int j = 1; j + 1 < m; ++j) {
            for(int k = j; k + 1 < m; ++k) {
                for(int f = i; f + 1 < n; ++f) {
                    if(mx[f][j][k] >= min(a[f][j - 1], a[f][k + 1])) break;
                    if(col[i][f][k] - col[i][f][j - 1] == k - j + 1) {
                        ++ans;
                        //cout << i << " " << j << " " << f << " " << k << "\n";
                    }
                }
            }
        }
    }
    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