oj.uz

답안 #595210

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
595210 2022-07-13T12:42:21 Z Apiram Sandcastle 2 (JOI22_ho_t5) C++14
0 / 100
 17 ms 6140 KB 
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y,cost,dir;
};
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,m;cin>>n>>m;
	vector<vector<int>>arr(n,vector<int>(m));
	vector<vector<vector<int>>>deg(n,vector<vector<int>>(m,vector<int>(4,0)));
	for (int i = 0;i<n;++i){
		for (int j = 0;j<m;++j){
			cin>>arr[i][j];
		}
	}
	vector<int>dx = {1,-1,0,0};
	vector<int>dy = {0,0,1,-1};
	for (int i = 0;i<n;++i){
		for (int j = 0;j < m;++j){
			for (int k = 0;k<4;++k){
				int nx = i + dx[k];
				int 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 (int i = 0;i<n;++i){
		for (int j = 0;j<m;++j){
			for (int 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();
		int nx = dx[u.dir] + u.x;
		int 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
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 17 ms 6140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -