HackerEarth Maximum Area problem solution

In this HackerEarth Maximum Area problem solution While walking around Hackerland, Marichka found a large square grid of size N . N consisting of unit squares of size 1 . 1. Now Marichka wants to explore it as much as possible.

In one move Marichka can move to the cell which shares an edge with cell, where Marichka currently is. It will take her aij (1 <= aij <= 10^6) minutes, where (i,j) is the coordinates of the cell where Marichka moved. Marichka defines her exploration level as the maximum row number for all cells she visited multiplied by maximum column number for all cells she visited. Marichka always starts her exploration in the cell with coordinates (1,1). Your task is to help Marichka maximize this score. Marichka is limited in time, so she can't spend more than T minutes exploring the grid.

HackerEarth Maximum Area problem solution.

#include <bits/stdc++.h>
#define PB push_back
#define LL long long
using namespace std;
const int INF = 1000 * 1000 * 1000;
LL d[151][150 * 150];
int N , T;
LL a[150][150];
int dx[4] = {1 , 0 , -1 , 0};
int dy[4] = {0 , 1 , 0 , -1};
bool inRange(int x , int y)
{
  return x >= 0 && x < N && y >= 0 && y < N;
}
void dijkstra(int idx , vector<int> start)
{
  //vector<int> d (n, INF),  p (n);
  //d[s] = 0;
  priority_queue < pair<LL,int> > q;
  for(auto x : start)
  {
    d[idx][x] = 0;
    q.push (make_pair (0, x));
  }
  while (!q.empty()) {
    int v = q.top().second; LL cur_d = -q.top().first;
    q.pop();
    if (cur_d > d[idx][v])  continue;
    int row = v / N;
    int column = v % N;
    for(int dir = 0; dir < 4; dir++)
    {
      int nR = row + dx[dir] , nC = column + dy[dir];
  
      if(!inRange(nR , nC))
        continue;
      int to = nR * N + nC , len = a[nR][nC];
      
      if (d[idx][v] + len < d[idx][to]) {
        d[idx][to] = d[idx][v] + len;
        q.push (make_pair (-d[idx][to], to));
      }
    }
  }
}
int main()
{
  cin >> N >> T;
  //Setting initial distances to INFININTY
  for(int i = 0; i <= N; i++)
    for(int j = 0; j < N; j++)
      for(int k = 0; k < N; k++)  
        d[i][j * N + k] = INF;
  //Reading the array a
  for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++)
      cin >> a[i][j];
  //Running the dijkstra from the starting point
  vector<int> start;
  start.PB(0);
  dijkstra(0 , start);
  //Running N dijstras from every column
  for(int i = 0; i < N; i++)
  {
    vector<int > v;
    for(int j = 0; j < N; j++)
      v.PB(i * N + j);
    dijkstra(i + 1, v);
  }
  //Updating answer using results from previous dijkstras
  int ans = 0;
  int ans2 = 0;
  for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++)
    {
      if(d[0][i * N + j] <= T)
        ans2 = max(ans2 , (i + 1) * (j + 1));
      for(int k = 0; k < min(N , 50); k++)
      {
        if(d[0][i * N + j] + d[k + 1][i * N + j] <= T)
        {
          ans = max(ans , (k + 1) * (j + 1));
          
        }
          
      }
    }
  cout << max(ans2 , ans2);
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 150;
int n, t, d[2][maxn][maxn], a[maxn][maxn];
int xs[] = {0, 0, +1, -1}, ys[] = {-1, +1, 0, 0};
struct State{
  int x, y, d;
  bool operator <(const State &o) const{
    return d < o.d;
  }
};
set<State> s;
void dij(int d[maxn][maxn]){
  while(s.size()){
    auto [x, y, di] = *s.begin();
    s.erase(s.begin());
    for(int i = 0; i < 4; i++){
      int nx = x + xs[i], ny = y + ys[i];
      if(nx >= 0 && ny >= 0 && nx < n && ny < n && d[nx][ny] > di + a[nx][ny]){
        s.erase({nx, ny, d[nx][ny]});
        d[nx][ny] = di + a[nx][ny];
        s.insert({nx, ny, d[nx][ny]});
      }
    }
  }
}
int ans;
void solve(){
  memset(d[0], 63, sizeof d[0]);
  s.insert({0, 0, d[0][0][0] = 0});
  dij(d[0]);
  for(int i = 0; i < n; i++){
    memset(d[1], 63, sizeof d[1]);
    for(int j = 0; j < n; j++)
      s.insert({i, j, d[1][i][j] = d[0][i][j]});
    dij(d[1]);
    for(int j = 0; j < n; j++)
      for(int k = 0; k < n; k++)
        if(d[1][j][k] <= t)
          ans = max(ans, (k + 1) * (i + 1));
  }
}
int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> t;
  for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      cin >> a[i][j];
  solve();
  for(int i = 0; i < n; i++)
    for(int j = 0; j < i; j++)
      swap(a[i][j], a[j][i]);
  solve();
  cout << ans << '\n';
}