Submission #53424

#	Time	Username	Problem	Language	Result	Execution time	Memory
53424		KieranHorgan	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	24 ms	31868 KiB

joioi

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
#define ll long long
#define int long long
#define ld long double
#define pii pair<int,int>
#define rand() abs((rand()<<15)|rand())
#define randll() abs(((long long)rand()<<30)|rand())
const int MOD = 998244353;

int grid[2005][2005];
int vis[2005][2005];

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long seed;
  asm("rdtsc" : "=A"(seed));
  srand(seed);

  int n, m;
  cin >> n >> m;

  multiset<int> rem;

  memset(grid, -1, sizeof(grid));
  int mi=1,mj=1;
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      cin >> grid[i][j];
      if(grid[i][j] > grid[mi][mj])
        mi=i,mj=j;
      rem.insert(grid[i][j]);
    }
  }

  int aMax = grid[mi][mj];
  int aMin = grid[mi][mj];

  int ans = 1ll<<40;
  priority_queue<pair<int, pair<int, int>>> pq;
  pq.push({grid[mi][mj], {mi, mj}});
  while(!pq.empty()) {
    int i = pq.top().second.first;
    int j = pq.top().second.second;
    grid[i][j] = pq.top().first;
    pq.pop();
    aMin = min(aMin, grid[i][j]);
    rem.erase(rem.find(grid[i][j]));
    if(rem.empty()) break;
    ans = min(ans, max(aMax-aMin, *rem.rbegin()-*rem.begin()));
    grid[i][j] = -1;
    if(grid[i-1][j  ]!=-1) {pq.push({grid[i-1][j  ], {i-1, j  }}); grid[i-1][j  ]=-1; };
    if(grid[i+1][j  ]!=-1) {pq.push({grid[i+1][j  ], {i+1, j  }}); grid[i+1][j  ]=-1; };
    if(grid[i  ][j-1]!=-1) {pq.push({grid[i  ][j-1], {i  , j-1}}); grid[i  ][j-1]=-1; };
    if(grid[i  ][j+1]!=-1) {pq.push({grid[i  ][j+1], {i  , j+1}}); grid[i  ][j+1]=-1; };
  }
  cout << ans << endl;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40