Submission #595214

#	Time	Username	Problem	Language	Result	Execution time	Memory
595214		Apiram	Sandcastle 2 (JOI22_ho_t5)	C++14	9 / 100	17 ms	9552 KiB

Main

#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 / 9
• Subtask 2: 0 / 10
• Subtask 3: 0 / 5
• Subtask 4: 0 / 56
• Subtask 5: 0 / 20