oj.uz

Submission #1060373

# Submission time Handle Problem Language Result Execution time Memory
1060373 2024-08-15T13:28:37 Z pera Maxcomp (info1cup18_maxcomp) C++17
15 / 100
 1 ms 348 KB 
#include<bits/stdc++.h>
using namespace std;
int main(){
   int n , m , ans = 0;
   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] = -1e9;
         }
      }
   };
   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]});
         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]});
         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]});
         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]});
         ans = max(ans , a[i][j] + i + j + mx[i][j]);
      }
   }
   cout << ans - 1 << endl;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 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 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 40.0

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