Submission #1060396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060396		pera	Maxcomp (info1cup18_maxcomp)	C++17	100 / 100	254 ms	24664 KiB

maxcomp

#include<bits/stdc++.h>
#define int long long
using namespace std;
main(){
   int n , m , ans = -1;
   cin >> n >> m;
   vector<vector<int>> a(n + 1 , vector<int>(m + 1)) , mx(n + 2 , vector<int>(m + 2));
   for(int i = 1;i <= n;i ++){
      for(int j = 1;j <= m;j ++){
         cin >> a[i][j];
      }
   }
   auto Reset = [&](){
      for(int i = 0;i <= n + 1;i ++){
         for(int j = 0;j <= m + 1;j ++){
            mx[i][j] = -1e16;
         }
      }
   };
   Reset();
   for(int i = 1;i <= n;i ++){
      for(int j = 1;j <= m;j ++){
         mx[i][j] = max({mx[i - 1][j] , mx[i][j - 1] , i + j - a[i][j] - 1});
         ans = max(ans , a[i][j] - i - j + mx[i][j]);
      }
   }
   Reset();
   for(int i = 1;i <= n;i ++){
      for(int j = m;j >= 1;j --){
         mx[i][j] = max({mx[i - 1][j] , mx[i][j + 1] , i - j - a[i][j] - 1});
         ans = max(ans , a[i][j] - i + j + mx[i][j]);
      }
   }
   Reset();
   for(int i = n;i >= 1;i --){
      for(int j = 1;j <= m;j ++){
         mx[i][j] = max({mx[i + 1][j] , mx[i][j - 1] , -i + j - a[i][j] - 1});
         ans = max(ans , a[i][j] + i - j + mx[i][j]);
      }
   }
   Reset();
   for(int i = n;i >= 1;i --){
      for(int j = m;j >= 1;j --){
         mx[i][j] = max({mx[i + 1][j] , mx[i][j + 1] , -i - j - a[i][j] - 1});
         ans = max(ans , a[i][j] + i + j + mx[i][j]);
      }
   }
   cout << ans << endl;
}

Compilation message (stderr)

maxcomp.cpp:4:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    4 | main(){
      | ^~~~

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