oj.uz

Submission #624778

# Submission time Handle Problem Language Result Execution time Memory
624778 2022-08-08T18:03:04 Z QwertyPi Sandcastle 2 (JOI22_ho_t5) C++14
10 / 100
 5000 ms 6432 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 5025 ms 6432 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 3 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 2 ms 308 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 3 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 2 ms 308 KB Output is correct
7 Execution timed out 5017 ms 468 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 3 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 2 ms 308 KB Output is correct
7 Execution timed out 5017 ms 468 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 3 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 2 ms 308 KB Output is correct
7 Execution timed out 5017 ms 468 KB Time limit exceeded
8 Halted 0 ms 0 KB -