Submission #526359

#	Time	Username	Problem	Language	Result	Execution time	Memory
526359		model_code	Sandcastle 2 (JOI22_ho_t5)	C++17	15 / 100	5090 ms	972 KiB

Main

// Time Complexity: O(H^3 * W^3)

#include <vector>
#include <iostream>
using namespace std;

long long solve(int H, int W, vector<vector<int> > A) {
	long long answer = 0;
	for (int lx = 0; lx < H; lx++) {
		for (int ly = 0; ly < W; ly++) {
			for (int rx = lx + 1; rx <= H; rx++) {
				for (int ry = ly + 1; ry <= W; ry++) {
					int cx = -1, cy = -1, maxval = -1;
					for (int i = lx; i < rx; i++) {
						for (int j = ly; j < ry; j++) {
							if (maxval < A[i][j]) {
								maxval = A[i][j];
								cx = i;
								cy = j;
							}
						}
					}
					int cnt = 0;
					while (true) {
						cnt++;
						int nx = -1, ny = -1, nxtval = -1;
						if (cx != lx && A[cx - 1][cy] < A[cx][cy] && nxtval < A[cx - 1][cy]) {
							nx = cx - 1; ny = cy; nxtval = A[cx - 1][cy];
						}
						if (cy != ly && A[cx][cy - 1] < A[cx][cy] && nxtval < A[cx][cy - 1]) {
							nx = cx; ny = cy - 1; nxtval = A[cx][cy - 1];
						}
						if (cx != rx - 1 && A[cx + 1][cy] < A[cx][cy] && nxtval < A[cx + 1][cy]) {
							nx = cx + 1; ny = cy; nxtval = A[cx + 1][cy];
						}
						if (cy != ry - 1 && A[cx][cy + 1] < A[cx][cy] && nxtval < A[cx][cy + 1]) {
							nx = cx; ny = cy + 1; nxtval = A[cx][cy + 1];
						}
						if (nxtval == -1) {
							break;
						}
						cx = nx; cy = ny;
					}
					if (cnt == (rx - lx) * (ry - ly)) {
						answer++;
					}
				}
			}
		}
	}
	return answer;
}

int main() {
	int H, W;
	cin >> H >> W;
	vector<vector<int> > A(H, vector<int>(W));
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> A[i][j];
		}
	}
	long long answer = solve(H, W, A);
	cout << answer << endl;
	return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 10 / 10
• Subtask 3: 5 / 5
• Subtask 4: 0 / 56
• Subtask 5: 0 / 20