oj.uz

Submission #526359

# Submission time Handle Problem Language Result Execution time Memory
526359 2022-02-14T13:13:43 Z model_code Sandcastle 2 (JOI22_ho_t5) C++17
15 / 100
 5000 ms 972 KB 
// 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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Execution timed out 5026 ms 632 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2044 ms 432 KB Output is correct
8 Correct 667 ms 428 KB Output is correct
9 Correct 174 ms 276 KB Output is correct
10 Correct 808 ms 284 KB Output is correct
11 Correct 2073 ms 284 KB Output is correct
12 Correct 1786 ms 348 KB Output is correct
13 Correct 340 ms 280 KB Output is correct
14 Correct 155 ms 280 KB Output is correct
15 Correct 361 ms 296 KB Output is correct
16 Correct 204 ms 296 KB Output is correct

Subtask #4
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2044 ms 432 KB Output is correct
8 Correct 667 ms 428 KB Output is correct
9 Correct 174 ms 276 KB Output is correct
10 Correct 808 ms 284 KB Output is correct
11 Correct 2073 ms 284 KB Output is correct
12 Correct 1786 ms 348 KB Output is correct
13 Correct 340 ms 280 KB Output is correct
14 Correct 155 ms 280 KB Output is correct
15 Correct 361 ms 296 KB Output is correct
16 Correct 204 ms 296 KB Output is correct
17 Execution timed out 5090 ms 972 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2044 ms 432 KB Output is correct
8 Correct 667 ms 428 KB Output is correct
9 Correct 174 ms 276 KB Output is correct
10 Correct 808 ms 284 KB Output is correct
11 Correct 2073 ms 284 KB Output is correct
12 Correct 1786 ms 348 KB Output is correct
13 Correct 340 ms 280 KB Output is correct
14 Correct 155 ms 280 KB Output is correct
15 Correct 361 ms 296 KB Output is correct
16 Correct 204 ms 296 KB Output is correct
17 Execution timed out 5090 ms 972 KB Time limit exceeded
18 Halted 0 ms 0 KB -