Submission #1203222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203222		ElayV13	Maxcomp (info1cup18_maxcomp)	C++20	30 / 100	1093 ms	1096 KiB

maxcomp

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e18;
const int N = 1001;

int n , m;
int a[N][N] , nw[N][N] , md[N][N] , dx[] = {1 , -1 , 0 , 0} , dy[] = {0 , 0 , 1 , -1};

signed main()
{
      ios_base::sync_with_stdio(0);cin.tie(0);
      cin >> n >> m;
      for(int i = 0;i < n;i++) for(int j = 0;j < m;j++) cin >> a[i][j];
      int res = -INF;
      for(int i = 0;i < n;i++)
      {
              for(int j = 0;j < m;j++)
              {
                      for(int _i = 0;_i < n;_i++)
                      {
                              for(int _j = 0;_j < m;_j++)
                              {
                                      if(a[i][j] < a[_i][_j]) continue;
                                      for(int ii  = 0;ii < n;ii++)
                                      {
                                              for(int jj = 0;jj < m;jj++)
                                              {
                                                      md[ii][jj] = INF;
                                                      nw[ii][jj] = (a[ii][jj] >= a[_i][_j] && a[ii][jj] <= a[i][j]);
                                              }
                                      }
                                      queue < pair < int , int > > q;
                                      md[i][j] = 0;
                                      q.push({i , j});
                                      while(!q.empty()){
                                                pair < int , int > p = q.front();
                                                q.pop();
                                                int x = p.first , y = p.second;
                                                for(int t = 0;t < 4;t++)
                                                {
                                                        int nx = x + dx[t] , ny = y + dy[t];
                                                        if(md[nx][ny] == INF && nw[nx][ny] == 1 && nx >= 0 && nx <= n - 1 && ny >= 0 && ny <= m - 1)
                                                        {
                                                                md[nx][ny] = md[x][y] + 1;
                                                                q.push({nx , ny});
                                                        }
                                                }
                                      }
                                      int val = a[i][j] - md[_i][_j] - a[_i][_j] - 1;
                                      if(md[_i][_j] != INF)
                                      res = max(res , val);
                              }
                      }
              }
      }
      cout << res << endl;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40