Submission #938098

#	Time	Username	Problem	Language	Result	Execution time	Memory
938098		esomer	Sandcastle 2 (JOI22_ho_t5)	C++17	19 / 100	5069 ms	924 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

bool adj(int i1, int j1, int i2, int j2){
	if(i1 != i2 && j1 != j2) return false;
	if(abs(i1-i2) > 1 || abs(j1 - j2) > 1) return false;
	return true;
}

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

	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];
		}
	}
	if(H == 1){
		long long ans = W;
		int l = 0;
		for(int i = 0; i < W; i++){
			ans += i - l;
			if(i < W - 1 && A[0][i] > A[0][i+1]) l = i + 1;
		}
		int r = W - 1;
		for(int i = W - 1; i >= 0; i--){
			ans += r - i;
			if(i > 0 && A[0][i] > A[0][i-1]) r = i - 1;
		}
		cout << ans << "\n";
	}else{
		long long ans = 0;
		for(int i = 0; i < H; i++){
			for(int j = 0; j < W; j++){
				for(int a = i; a < H; a++){
					for(int b = j; b < W; b++){
						vector<tuple<int, int, int>> all;
						for(int l = i; l <= a; l++){
							for(int m = j; m <= b; m++){
								all.push_back({A[l][m], l, m});
							}
						}
						sort(all.begin(), all.end());
						bool gd = true;
						for(int n = 1; n < (int)all.size(); n++){
							int i1 = get<1>(all[n-1]);
							int j1 = get<2>(all[n-1]);
							int i2 = get<1>(all[n]);
							int j2 = get<2>(all[n]);
							if(!adj(i1, j1, i2, j2)) gd = false;
						}
						if(gd) ans++;
					}
				}
			}
		}
		cout << ans << "\n";
	}
}

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