Submission #1181730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181730		jbareja	Sandcastle 2 (JOI22_ho_t5)	C++20	19 / 100	5094 ms	1412 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int H; // liczba wierszy
int W; // liczba kolumn

vector<vector<int>> height;
vector<vector<bool>> visited;

vector<pair<int,int>> moves = { {-1,0}, {1,0}, {0,-1}, {0,1} };

ll formula_1_x_W(ll x) {
	return x * (x-1) / 2;
}

void subtask_1() {
	ll ans = W;
	ll cnt = 1;
	vector<int> extremes = { 1 };
	for (int i=2; i<=W-1; i++)
		if ((height[1][i-1] < height[1][i] && height[1][i] > height[1][i+1]) || (height[1][i-1] > height[1][i] && height[1][i] < height[1][i+1]))
			extremes.push_back(i);
	extremes.push_back(W);

	for (int i=0; i<extremes.size()-1; i++) ans += formula_1_x_W(extremes[i+1] - extremes[i] + 1);

	cout << ans << '\n';
}

bool in_range(int vi, int vj, int i1, int j1, int i2, int j2) {
	return i1 <= vi && vi <= i2 && j1 <= vj && vj <= j2;
}

void dfs(int vi, int vj, int i1, int j1, int i2, int j2) {
	visited[vi][vj] = true;
	height[0][0] = INT_MIN;
	int mi = 0, mj = 0;
	for (const auto& [di, dj]: moves) if (in_range(vi+di,vj+dj, i1,j1, i2,j2) && !visited[vi+di][vj+dj] && height[vi+di][vj+dj] < height[vi][vj]) {
		if (height[mi][mj] < height[vi+di][vj+dj]) mi = vi+di, mj = vj+dj;
	}
	if (mi == 0 && mj == 0) return;
	dfs(mi,mj, i1,j1, i2,j2);
}

void visualize(int i1, int j1, int i2, int j2) {
	for (int i=1; i<=H; i++) {
		for (int j=1; j<=W; j++) {
			if (in_range(i,j, i1,j1, i2,j2)) cout << '#';
			else cout << '.';
		}
		cout << '\n';
	}
	cout << '\n';
}

bool check(int i1, int j1, int i2, int j2) {
	int vi = i1;
	int vj = j1;
	for (int i=i1; i<=i2; i++) for (int j=j1; j<=j2; j++) {
		visited[i][j] = false;
		if (height[i][j] > height[vi][vj]) vi = i, vj = j;
	}
	dfs(vi,vj, i1,j1, i2,j2);
	for (int i=i1; i<=i2; i++) for (int j=j1; j<=j2; j++) if (!visited[i][j]) return false;
	// visualize(i1, j1, i2, j2);
	return true;
}

void subtask_2() {
	int ans = 0;
	for (int i1=1; i1<=H; i1++) for (int j1=1; j1<=W; j1++) for (int i2=i1; i2<=H; i2++) for (int j2=j1; j2<=W; j2++)
		ans += check(i1,j1,i2,j2);
	cout << ans << '\n';
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> H >> W;
	height.assign(H+2, vector<int>(W+2, 0));
	visited.assign(H+2, vector<bool>(W+2, false));

	for (int i=1; i<=H; i++) for (int j=1; j<=W; j++) cin >> height[i][j];

	if (H == 1) { subtask_1(); return 0; }
	subtask_2();
}

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