#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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
