Submission #636890

#	Time	Username	Problem	Language	Result	Execution time	Memory
636890		Dec0Dedd	Maxcomp (info1cup18_maxcomp)	C++14	15 / 100	1 ms	468 KiB

maxcomp

#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
• Subtask 2: 15 / 15
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40