Submission #1290968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290968		gustavo_d	Rectangles (IOI19_rect)	C++20	27 / 100	5090 ms	24720 KiB

rect

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

#pragma GCC optimize("O3,unroll-loops,inline-functions")

#define sz(v) (int)(v).size()

typedef long long ll;

const int MAXN = 700;
const int INF = 1e9;

ll sum(ll x) {
	return x * (x+1) / 2;
}

int mat[MAXN][MAXN];
int n, m;

ll count_rectangles(vector<vector<int>> input) {
	n = sz(input); m = sz(input[0]);

	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) mat[i][j] = input[i][j];
	}

	ll ans = 0;
	for (int i1=1; i1<n-1; i1++) {
		for (int i2=i1; i2<n-1; i2++) {
			for (int j1=1; j1<m-1; j1++) {
				vector<int> mx(n, -INF);
				for (int j2=j1; j2<m-1; j2++) {
					bool can = true, stop = false;
					for (int i=i1; i<=i2; i++) {
						if (mat[i][j2] >= min(mat[i1-1][j2], mat[i2+1][j2])) {
							can = false;
							stop = true;
						}
						mx[i] = max(mx[i], mat[i][j2]);
						if (mx[i] >= mat[i][j1-1]) can = false, stop = true;
						if (mx[i] >= mat[i][j2+1]) can = false;
					}
					if (stop) break;
					ans += can;
				}
			}
		}
	}

	return ans;
}

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