oj.uz

Submission #636890

# Submission time Handle Problem Language Result Execution time Memory
636890 2022-08-30T11:35:26 Z Dec0Dedd Maxcomp (info1cup18_maxcomp) C++14
15 / 100
 1 ms 468 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 1e3+100;
const ll INF = 1e18;
const int di[] = {-1, -1, 1, 1};
const int dj[] = {-1, 1, 1, -1};

ll a[N][N], p[4][N][N], n, m;

int main() {
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);
   cout.tie(NULL);
   
   cin>>n>>m;
   for (int i=1; i<=n; ++i) {
      for (int j=1; j<=m; ++j) cin>>a[i][j];
   }

   for (int k=0; k<4; ++k) {
      for (int i=0; i<=n+1; ++i) {
         for (int j=0; j<=m+1; ++j) p[k][i][j]=INF;
      }
   }

   // 0
   for (int i=1; i<=n; ++i) {
      for (int j=1; j<=m; ++j) {
         p[0][i][j]=min({p[0][i-1][j], p[0][i][j-1], a[i][j]+i*di[0]+j*dj[0]});
      }
   }

   // 1
   for (int i=1; i<=n; ++i) {
      for (int j=m; j>=1; --j) {
         p[1][i][j]=min({p[1][i-1][j], p[1][i][j+1], a[i][j]+i*di[1]+j*dj[1]});
      }
   }

   // 2
   for (int i=n; i>=1; --i) {
      for (int j=m; j>=1; --j) {
         p[2][i][j]=min({p[2][i+1][j], p[2][i][j+1], a[i][j]+i*di[2]+j*di[2]});
      }
   }

   // 3
   for (int i=n; i>=1; --i) {
      for (int j=1; j<=m; ++j) {
         p[3][i][j]=min({p[3][i+1][j], p[3][i][j-1], a[i][j]+i*di[3]+j*dj[3]});
      }
   }

   ll ans=0;
   for (int i=1; i<=n; ++i) {
      for (int j=1; j<=m; ++j) {
         for (int k=0; k<4; ++k) {
            ans=max(ans, a[i][j]+di[k]*i+dj[k]*j-p[k][i][j]-1);
         }
      }
   }

   cout<<ans<<"\n";
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -