Submission #340548

#	Time	Username	Problem	Language	Result	Execution time	Memory
340548		FlashGamezzz	Rectangles (IOI19_rect)	C++17	37 / 100	5075 ms	234628 KiB

rect

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <unordered_set>
#include <vector>
#include <utility>
#include "rect.h"

using namespace std;

int n, m;
vector<vector<vector<bool> > > val, val2;

long long count_rectangles(vector<vector<int> > a) {
	n = a.size(); m = a[0].size(); long long ans = 0;
	val.push_back(vector<vector<bool> >()); val2.push_back(vector<vector<bool> >());
	for (int r = 1; r < n-1; r++){
		val.push_back(vector<vector<bool> >()); val[r].push_back(vector<bool>());
		for (int cs = 1; cs < m-1; cs++){
			val[r].push_back(vector<bool>()); int maxv = 0;
			for (int t = 0; t < cs; t++){
				val[r][cs].push_back(false);
			}
			for (int ce = cs; ce < m-1; ce++){
				maxv = max(maxv, a[r][ce]);
				if (maxv < a[r][cs-1] && maxv < a[r][ce+1]){
					val[r][cs].push_back(true);
				} else {
					val[r][cs].push_back(false);
				}
			}
		}
	}
	for (int c = 1; c < m-1; c++){
		val2.push_back(vector<vector<bool> >()); val2[c].push_back(vector<bool>());
		for (int rs = 1; rs < n-1; rs++){
			val2[c].push_back(vector<bool>()); int maxv = 0;
			for (int t = 0; t < rs; t++){
				val2[c][rs].push_back(false);
			}
			for (int re = rs; re < n-1; re++){
				maxv = max(maxv, a[re][c]);
				if (maxv < a[rs-1][c] && maxv < a[re+1][c]){
					val2[c][rs].push_back(true);
				} else {
					val2[c][rs].push_back(false);
				}
			}
		}
	}
	for (int rs = 1; rs < n-1; rs++){
		for (int cs = 1; cs < m-1; cs++){
			for (int ce = cs; ce < m-1; ce++){
				for (int re = rs; re < n-1; re++){
					if (val[re][cs][ce]){
						bool valid = true;
						for (int i = cs; i <= ce; i++){
							if (!val2[i][rs][re]){
								valid = false;
							}
						}
						if (valid){
							ans++;
						}
					} else {
						break;
					}
				}
			}
		}
	}
	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