oj.uz

답안 #260741

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
260741 2020-08-10T20:05:17 Z idk321 Rectangles (IOI19_rect) Java 11
15 / 100
 5000 ms 1048576 KB 
import java.util.Arrays;

class rect {
	boolean[][] visited;

	public long count_rectangles(int[][] a) {
		int n = a.length;
		int m = a[0].length;
		int[][] dpUp = new int[n][m];
		int[][] dpDown = new int[n][m];
		int[][] dpLeft = new int[n][m];
		int[][] dpRight = new int[n][m];

		for (int i = 1; i < n - 1; i++) {
			for (int j = m - 2; j > 0; j--) {
				if (a[i - 1][j] > a[i][j]) dpUp[i][j] = dpUp[i][j + 1] + 1;
				if (a[i + 1][j] > a[i][j]) dpDown[i][j] = dpDown[i][j + 1] + 1;
			}
		}
		for (int i = n - 2; i > 0; i--) {
			for (int j = 1; j < m - 1; j++) {
				if (a[i][j + 1] > a[i][j]) dpRight[i][j] = dpRight[i + 1][j] + 1;
				if (a[i][j - 1] > a[i][j]) dpLeft[i][j] = dpLeft[i + 1][j] + 1;
			}
		}

		if (n <= 2 || m <= 2) return 0;

		boolean allZeroAndOne = true;
		for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (a[i][j] != 0 && a[i][j] != 1) allZeroAndOne = false;

		if (n <= 3) {
			int currLength = 0;
			int goodStarts = 0;
			long res = 0;
			for (int i = 1; i < m - 1; i++) {
				int h = a[1][i];
				if (a[0][i] <= h || a[2][i] <= h) {
					goodStarts = 0;
				} else {
					if (a[1][i - 1] > h) goodStarts++;
					if (a[1][i + 1] > h) res += goodStarts;
				}
			}

			return res;
		/*} else if (allZeroAndOne) {
			visited = new boolean[n][m];
			Arrays.fill(visited[0], true);
			Arrays.fill(visited[n - 1], true);
			for (int i = 0; i < n; i++) {
				visited[i][0] = true;
				visited[i][m - 1] = true;
			}
			for (int i = 1; i < n - 1; i++) {
				for (int j = 1; j < m - 1; j++) {

				}
			} */
		} else {
			int[][][] maxRight = new int[n][m][m];
			for (int i = 1; i < n - 1; i++) {
				for (int j = 1; j < m - 1; j++) {
					for (int k = j; k < m - 1; k++) {
						if (j == k) {
							maxRight[i][j][k] = a[i][j];
						} else {
							maxRight[i][j][k] = Math.max(a[i][k], maxRight[i][j][k - 1]);
						}
					}
				}
			}
			boolean[][][][] rightOk = new boolean[n][n][m][m];
			for (int i = 1; i < n - 1; i++) {
				for (int k = i; k < n - 1; k++) {
					for (int j = 1;  j < m - 1; j++) {
						for (int l = j; l < m - 1; l++) {
							rightOk[i][k][j][l] = maxRight[k][j][l] < a[k][l + 1];
							if (k != i) {
								rightOk[i][k][j][l] = rightOk[i][k][j][l] && rightOk[i][k - 1][j][l];
							}
						}
					}
				}
			}
			boolean[][][][] leftOk = new boolean[n][n][m][m];
			for (int i = 1; i < n - 1; i++) {
				for (int k = i; k < n - 1; k++) {
					for (int j = 1;  j < m - 1; j++) {
						for (int l = j; l < m - 1; l++) {
							leftOk[i][k][j][l] = maxRight[k][j][l] < a[k][j - 1];
							if (k != i) {
								leftOk[i][k][j][l] = rightOk[i][k][j][l] && rightOk[i][k - 1][j][l];
							}
						}
					}
				}
			}

			int[][][] maxDown = new int[m][n][n];
			for (int j = 1; j < m - 1; j++) {
				for (int i = 1; i < n - 1; i++) {
					for (int k = i; k < n - 1; k++) {
						if (i == k) {
							maxDown[j][i][k] = a[i][j];
						} else {
							maxDown[j][i][k] = Math.max(a[k][j], maxDown[j][i][k - 1]);
						}
					}
				}
			}

			long rect = 0;
			for (int i = 1; i < n - 1; i++) {
				for (int j = 1; j < m - 1; j++) {
					for (int k = i; k < n - 1; k++) {
						if (a[k][j - 1] <= a[k][j]) break;
						for (int l = j; l < m - 1; l++) {
							if (maxDown[l][i][k] >= a[k + 1][l]) break;
							if (maxDown[l][i][k] >= a[i - 1][l]) break;


 							if ((rightOk[i][k][j][l] && leftOk[i][k][j][l]) && checkIfGood(a, i, j, k, l)) {
								rect++;
								//System.out.println(i + " " + j + " " + k + " " + l);
							}
						}
					}
				}
			}
			//System.out.println(Arrays.deepToString(maxDown));
			//System.out.println(Arrays.deepToString(rightOk));
			//System.out.println(maxDown[1][1][1]);

			return rect;
		}
	}


	private boolean checkIfGood(int[][] ar, int a, int b, int c, int d) {

		for (int i = a; i <= c; i++) {
			int max = 0;
			for (int j = b; j <= d; j++) {
				max = Math.max(max, ar[i][j]);
			}
			if (ar[i][d + 1] <= max) return false;
			if (ar[i][b - 1] <= max) return false;
		}
		for (int j = b; j <= d; j++) {
			int max = 0;
			for (int i = a; i <= c; i++) {
				max = Math.max(max, ar[i][j]);
			}
			if (ar[c + 1][j] <= max) return false;
			if (ar[a - 1][j] <= max) return false;
		}

		return true;
	}
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 10344 KB Output is correct
2 Correct 166 ms 16800 KB Output is correct
3 Correct 182 ms 16464 KB Output is correct
4 Correct 176 ms 16848 KB Output is correct
5 Correct 124 ms 14696 KB Output is correct
6 Correct 122 ms 14856 KB Output is correct
7 Correct 96 ms 12428 KB Output is correct
8 Correct 88 ms 10848 KB Output is correct
9 Correct 113 ms 14824 KB Output is correct
10 Correct 121 ms 15104 KB Output is correct
11 Correct 121 ms 15044 KB Output is correct
12 Correct 123 ms 14600 KB Output is correct
13 Correct 74 ms 10212 KB Output is correct
14 Correct 77 ms 10216 KB Output is correct
15 Correct 78 ms 10216 KB Output is correct
16 Correct 77 ms 10104 KB Output is correct
17 Correct 79 ms 10104 KB Output is correct
18 Correct 79 ms 10232 KB Output is correct
19 Correct 135 ms 15072 KB Output is correct
20 Correct 96 ms 11056 KB Output is correct
21 Correct 86 ms 10328 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 10344 KB Output is correct
2 Correct 166 ms 16800 KB Output is correct
3 Correct 182 ms 16464 KB Output is correct
4 Correct 176 ms 16848 KB Output is correct
5 Correct 124 ms 14696 KB Output is correct
6 Correct 122 ms 14856 KB Output is correct
7 Correct 96 ms 12428 KB Output is correct
8 Correct 88 ms 10848 KB Output is correct
9 Correct 113 ms 14824 KB Output is correct
10 Correct 121 ms 15104 KB Output is correct
11 Correct 121 ms 15044 KB Output is correct
12 Correct 123 ms 14600 KB Output is correct
13 Correct 74 ms 10212 KB Output is correct
14 Correct 77 ms 10216 KB Output is correct
15 Correct 78 ms 10216 KB Output is correct
16 Correct 77 ms 10104 KB Output is correct
17 Correct 1434 ms 133580 KB Output is correct
18 Correct 1342 ms 129288 KB Output is correct
19 Correct 2058 ms 130212 KB Output is correct
20 Correct 1593 ms 133868 KB Output is correct
21 Correct 1854 ms 129008 KB Output is correct
22 Correct 1851 ms 127724 KB Output is correct
23 Correct 1840 ms 129904 KB Output is correct
24 Correct 341 ms 47236 KB Output is correct
25 Correct 79 ms 10104 KB Output is correct
26 Correct 79 ms 10232 KB Output is correct
27 Correct 135 ms 15072 KB Output is correct
28 Correct 96 ms 11056 KB Output is correct
29 Correct 86 ms 10328 KB Output is correct

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 10344 KB Output is correct
2 Correct 166 ms 16800 KB Output is correct
3 Correct 182 ms 16464 KB Output is correct
4 Correct 176 ms 16848 KB Output is correct
5 Correct 124 ms 14696 KB Output is correct
6 Correct 122 ms 14856 KB Output is correct
7 Correct 96 ms 12428 KB Output is correct
8 Correct 88 ms 10848 KB Output is correct
9 Correct 113 ms 14824 KB Output is correct
10 Correct 121 ms 15104 KB Output is correct
11 Correct 121 ms 15044 KB Output is correct
12 Correct 123 ms 14600 KB Output is correct
13 Correct 74 ms 10212 KB Output is correct
14 Correct 77 ms 10216 KB Output is correct
15 Correct 78 ms 10216 KB Output is correct
16 Correct 77 ms 10104 KB Output is correct
17 Correct 1434 ms 133580 KB Output is correct
18 Correct 1342 ms 129288 KB Output is correct
19 Correct 2058 ms 130212 KB Output is correct
20 Correct 1593 ms 133868 KB Output is correct
21 Correct 1854 ms 129008 KB Output is correct
22 Correct 1851 ms 127724 KB Output is correct
23 Correct 1840 ms 129904 KB Output is correct
24 Correct 341 ms 47236 KB Output is correct
25 Execution timed out 5090 ms 1023036 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 10344 KB Output is correct
2 Correct 166 ms 16800 KB Output is correct
3 Correct 182 ms 16464 KB Output is correct
4 Correct 176 ms 16848 KB Output is correct
5 Correct 124 ms 14696 KB Output is correct
6 Correct 122 ms 14856 KB Output is correct
7 Correct 96 ms 12428 KB Output is correct
8 Correct 88 ms 10848 KB Output is correct
9 Correct 113 ms 14824 KB Output is correct
10 Correct 121 ms 15104 KB Output is correct
11 Correct 121 ms 15044 KB Output is correct
12 Correct 123 ms 14600 KB Output is correct
13 Correct 74 ms 10212 KB Output is correct
14 Correct 77 ms 10216 KB Output is correct
15 Correct 78 ms 10216 KB Output is correct
16 Correct 77 ms 10104 KB Output is correct
17 Correct 1434 ms 133580 KB Output is correct
18 Correct 1342 ms 129288 KB Output is correct
19 Correct 2058 ms 130212 KB Output is correct
20 Correct 1593 ms 133868 KB Output is correct
21 Correct 1854 ms 129008 KB Output is correct
22 Correct 1851 ms 127724 KB Output is correct
23 Correct 1840 ms 129904 KB Output is correct
24 Correct 341 ms 47236 KB Output is correct
25 Execution timed out 5090 ms 1023036 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 10728 KB Output is correct
2 Correct 84 ms 10600 KB Output is correct
3 Correct 82 ms 10232 KB Output is correct
4 Correct 77 ms 10088 KB Output is correct
5 Incorrect 85 ms 10652 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 10360 KB Output is correct
2 Runtime error 4311 ms 1048576 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 10344 KB Output is correct
2 Correct 166 ms 16800 KB Output is correct
3 Correct 182 ms 16464 KB Output is correct
4 Correct 176 ms 16848 KB Output is correct
5 Correct 124 ms 14696 KB Output is correct
6 Correct 122 ms 14856 KB Output is correct
7 Correct 96 ms 12428 KB Output is correct
8 Correct 88 ms 10848 KB Output is correct
9 Correct 113 ms 14824 KB Output is correct
10 Correct 121 ms 15104 KB Output is correct
11 Correct 121 ms 15044 KB Output is correct
12 Correct 123 ms 14600 KB Output is correct
13 Correct 74 ms 10212 KB Output is correct
14 Correct 77 ms 10216 KB Output is correct
15 Correct 78 ms 10216 KB Output is correct
16 Correct 77 ms 10104 KB Output is correct
17 Correct 1434 ms 133580 KB Output is correct
18 Correct 1342 ms 129288 KB Output is correct
19 Correct 2058 ms 130212 KB Output is correct
20 Correct 1593 ms 133868 KB Output is correct
21 Correct 1854 ms 129008 KB Output is correct
22 Correct 1851 ms 127724 KB Output is correct
23 Correct 1840 ms 129904 KB Output is correct
24 Correct 341 ms 47236 KB Output is correct
25 Execution timed out 5090 ms 1023036 KB Time limit exceeded
26 Halted 0 ms 0 KB -