제출 #1288518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288518		kaiboy	Sandcastle 2 (JOI22_ho_t5)	C++20	100 / 100	1407 ms	180472 KiB

Main

// coached by rainboy
#include <algorithm>
#include <iostream>

using namespace std;

const int     N = 50000;
const int ddi[] = { -1, 1, 0, 0 };
const int ddj[] = { 0, 0, -1, 1 };

int *aa[N];
bool *good[3][3][3][3][N];
int *ss[3][3][N], kk[3][3][N], kk_[N + 1];

bool check(int i, int j, int il, int ir, int jl, int jr) {
	return good[min(i - il, 2)][min(ir - i, 2)][min(j - jl, 2)][min(jr - j, 2)][i][j];
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, m; cin >> n >> m;
	int n_ = n, m_ = m;
	bool swapped = false;
	if (n < m)
		swap(n, m), swapped = true;
	for (int i = 0; i < n; i++)
		aa[i] = new int[m];
	for (int i = 0; i < n_; i++)
		for (int j = 0; j < m_; j++)
			if (!swapped)
				cin >> aa[i][j];
			else
				cin >> aa[j][i];
	for (int n0 = 0; n0 <= 2; n0++)
		for (int n1 = 0; n1 <= 2; n1++)
			for (int m0 = 0; m0 <= 2; m0++)
				for (int m1 = 0; m1 <= 2; m1++)
					for (int i = n0; i + n1 < n; i++) {
						good[n0][n1][m0][m1][i] = new bool[m];
						for (int j = m0; j + m1 < m; j++) {
							int il = i - n0, ir = i + n1;
							int jl = j - m0, jr = j + m1;
							bool yes = false;
							for (int h = 0; h < 4; h++) {
								int i0 = i + ddi[h], j0 = j + ddj[h];
								if (il <= i0 && i0 <= ir && jl <= j0 && j0 <= jr) {
									int i_ = -1, j_ = -1;
									for (int h_ = 0; h_ < 4; h_++) {
										int i1 = i0 + ddi[h_], j1 = j0 + ddj[h_];
										if (il <= i1 && i1 <= ir && jl <= j1 && j1 <= jr
												&& aa[i1][j1] < aa[i0][j0] && (i_ == -1 || aa[i_][j_] < aa[i1][j1]))
											i_ = i1, j_ = j1;
									}
									if (i_ == i && j_ == j)
										yes = true;
								}
							}
							good[n0][n1][m0][m1][i][j] = yes;
						}
					}
	for (int n0 = 0; n0 <= 2; n0++)
		for (int n1 = 0; n1 <= 2; n1++)
			for (int i = n0; i + n1 < n; i++) {
				ss[n0][n1][i] = new int[m];
				for (int j = 0; j < m; j++)
					ss[n0][n1][i][j] = !check(i, j, i - n0, i + n1, 0, m - 1);
				for (int j = 1; j < m; j++)
					ss[n0][n1][i][j] += ss[n0][n1][i][j - 1];
			}
	int ans = 0;
	for (int jl = 0; jl < m; jl++)
		for (int jr = jl; jr < m; jr++) {
			for (int n0 = 0; n0 <= 2; n0++)
				for (int n1 = 0; n1 <= 2; n1++)
					for (int i = n0; i + n1 < n; i++) {
						int il = i - n0, ir = i + n1, k = 0;
						if (jr - jl + 1 > 4) {
							for (int j = jl; j <= jl + 1; j++)
								k += !check(i, j, il, ir, jl, jr);
							k += ss[n0][n1][i][jr - 2] - ss[n0][n1][i][jl + 1];
							for (int j = jr - 1; j <= jr; j++)
								k += !check(i, j, il, ir, jl, jr);
						} else
							for (int j = jl; j <= jr; j++)
								k += !check(i, j, il, ir, jl, jr);
						kk[n0][n1][i] = k;
					}
			for (int s = 0; s <= n * m; s++)
				kk_[s] = 0;
			for (int s = 0, ir = 0; ir < n; ir++) {
				for (int il = max(ir - 2, 0); il <= ir; il++) {
					int k = 0;
					for (int i_ = il; i_ <= ir; i_++)
						k += kk[i_ - il][ir - i_][i_];
					if (k == 1)
						ans++;
				}
				if (ir >= 3) {
					int p = s;
					for (int i_ = ir - 1; i_ <= ir; i_++)
						p += kk[2][ir - i_][i_];
					int q = s;
					for (int i_ = ir - 3; i_ <= ir - 2; i_++)
						q -= kk[i_ - (ir - 3)][2][i_];
					if (q >= -1)
						kk_[q + 1]++;
					ans += kk_[p];
					if (ir + 1 < n)
						s += kk[2][2][ir - 1];
				}
			}
		}
	cout << ans << '\n';
	return 0;
}

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