Submission #624778

#	Time	Username	Problem	Language	Result	Execution time	Memory
624778		QwertyPi	Sandcastle 2 (JOI22_ho_t5)	C++14	10 / 100	5025 ms	6432 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;

int a[50013];

int h, w;
int id(int i, int j){
	return i * w + j;
}

int32_t main(){
	cin >> h >> w;
	for(int i = 0; i < h * w; i++){
		cin >> a[i];
	}
	{
		set<int> S; map<int, int> M;
		for(int i = 0; i < h * w; i++){
			S.insert(a[i]);
		}
		int idx = 0;
		for(auto j : S){
			M[j] = idx++;
		}
		for(int i = 0; i < h * w; i++){
			a[i] = M[a[i]];
		}
	}
	
	int ans = 0;
	for(int u = 0; u < h; u++){
		for(int b = u; b < h; b++){
			for(int l = 0; l < w; l++){
				for(int r = l; r < w; r++){
					int x = u, y = l; int cnt = 1;
					for(int i = u; i <= b; i++){
						for(int j = l; j <= r; j++){
							if(a[id(i, j)] > a[id(x, y)])
								x = i, y = j;
						}
					}
					while(cnt != (u - b + 1) * (r - l + 1)){
						int nx = -1, ny = -1;
						for(auto dir : vector<pair<int, int>> {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}){
							int rx = x + dir.first, ry = y + dir.second;
							if(rx > b || rx < u || ry > r || ry < l || a[id(rx, ry)] > a[id(x, y)]) continue;
							if(nx == -1 || a[id(nx, ny)] < a[id(rx, ry)]) nx = rx, ny = ry;
						}
						if(nx == -1) break;
						x = nx, y = ny;
						cnt++;
					}
					if(cnt == (b - u + 1) * (r - l + 1)){
						ans++;
					}
				}
			}
		}
	}
	cout << ans << endl;
}

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