oj.uz

답안 #536159

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
536159 2022-03-12T14:27:05 Z cig32 Maxcomp (info1cup18_maxcomp) C++17
15 / 100
 6 ms 348 KB 
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}

void solve(int tc) {
  int n, m;
  cin >> n >> m;
  int a[n+1][m+1];
  for(int i=1; i<=n; i++) {
    for(int j=1; j<=m; j++) {
      cin >> a[i][j];
    }
  }
  int ans = 0;
  for(int i=1; i<=n; i++) {
    for(int j=1; j<=m; j++) {
      int mi = a[i][j];
      bool can[n*m + 1];
      for(int k=1; k<=n; k++) {
        for(int l=1; l<=m; l++) {
          can[(k-1)*m + l] = (a[k][l] >= mi ? 1 : 0);
        }
      }
      bool vis[n*m + 1];
      int dist[n*m + 1];
      for(int k=1; k<=n*m; k++) vis[k] = 0, dist[k] = 1e18;
      dist[(i-1)*m + j] = 1;
      queue<int> q;
      q.push((i-1)*m + j);
      while(q.size()) {
        int f=q.front(); q.pop();
        if(!vis[f]) {
          vis[f] = 1;
          vector<pair<int, int> > dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
          for(pair<int, int> x: dirs) {
            int old_r = (f-1) / m + 1, old_c = (f-1) % m + 1;
            old_r += x.first, old_c += x.second;
            if(min(old_r, old_c) >= 1 && old_r <= n && old_c <= m) {
              int id = (old_r-1) * m + old_c;
              if(!vis[id] && can[id] && dist[id] > dist[f] + 1) {
                dist[id] = dist[f] + 1;
                q.push(id);
              }
            }
          }
        }
      }
      for(int k=1; k<=n; k++) {
        for(int l=1; l<=m; l++) {
          if(can[(k-1)*m + l] && dist[(k-1)*m + l] != 1e18) {
            ans = max(ans, a[k][l] - mi - dist[(k-1)*m + l]);
          }
        }
      }
    }
  }
  cout << ans << "\n";
}

int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}

Subtask #1
0 / 15.0

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

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Correct 5 ms 348 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 40.0

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