oj.uz

Submission #595214

# Submission time Handle Problem Language Result Execution time Memory
595214 2022-07-13T12:43:10 Z Apiram Sandcastle 2 (JOI22_ho_t5) C++14
9 / 100
 17 ms 9552 KB 
#include<bits/stdc++.h>
using namespace std;
struct node{
	long long x,y,cost,dir;
};
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	long long n,m;cin>>n>>m;
	vector<vector<long long>>arr(n,vector<long long>(m));
	vector<vector<vector<long long>>>deg(n,vector<vector<long long>>(m,vector<long long>(4,0)));
	for (long long i = 0;i<n;++i){
		for (long long j = 0;j<m;++j){
			cin>>arr[i][j];
		}
	}
	vector<long long>dx = {1,-1,0,0};
	vector<long long>dy = {0,0,1,-1};
	for (long long i = 0;i<n;++i){
		for (long long j = 0;j < m;++j){
			for (long long k = 0;k<4;++k){
				long long nx = i + dx[k];
				long long ny = j + dy[k];
				if (nx>=0 && nx < n&& ny>=0 && ny < m){
					if (arr[nx][ny] < arr[i][j]){
						deg[nx][ny][k]++;
					}
				}
			}
		}
	}
	queue<node>q;
	for (long long i = 0;i<n;++i){
		for (long long j = 0;j<m;++j){
			for (long long k = 0;k<4;++k){
				if (deg[i][j][k] == 0){
					q.push({i,j,1,k});
				}
			}
		}
	}
	long long ans = n * m;
	while(!q.empty()){
		auto u = q.front();
		q.pop();
		long long nx = dx[u.dir] + u.x;
		long long ny = dy[u.dir] + u.y;
		bool ok = false;
		if (nx>=0 && nx < n&& ny>=0 && ny < m){
			if (arr[nx][ny] < arr[u.x][u.y]){
				q.push({nx,ny,u.cost + 1,u.dir});
				ok = true;
			}
		}
		if (!ok){
			ans+=u.cost * (u.cost + 1) / 2 - u.cost;
		}
	}
	cout<<ans<<'\n';
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 16 ms 9548 KB Output is correct
3 Correct 15 ms 9300 KB Output is correct
4 Correct 16 ms 9448 KB Output is correct
5 Correct 17 ms 9524 KB Output is correct
6 Correct 17 ms 9552 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -