oj.uz

Submission #922999

# Submission time Handle Problem Language Result Execution time Memory
922999 2024-02-06T12:17:46 Z Ianis Maxcomp (info1cup18_maxcomp) C++17
100 / 100
 93 ms 17228 KB 
#ifdef LOCAL
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <random>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#else
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define cerr if (false) cerr 
#define endl '\n'
#endif

#define fi first
#define se second

#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))

#define bit(mask, i) (((mask) >> (i)) & 1)
#define popcount(x) __builtin_popcount(x)

#define YES cout << "YES" << endl
#define NO cout << "NO" << endl

using namespace std;

template <typename T>
bool ckmax(T &a, T b) { return a < b ? a = b, true : false; }
template <typename T>
bool ckmin(T &a, T b) { return a > b ? a = b, true : false; }

using ll = long long;
using pii = pair<int, int>;

const int NMAX = 1005;
const int INF  = 1e9+5;

int n, m;
int a[NMAX][NMAX];
int dp[NMAX][NMAX];

void read() {
   cin >> n >> m;
   for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++)
         cin >> a[i][j];
   }
}

void reset() {
   for (int i = 0; i <= n + 1; i++)
      fill(dp[i], dp[i] + m + 2, INF);
}

int solve() {
   int ans = -1;

   reset();
   for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
         dp[i][j] = a[i][j] + 1;
         ckmin(dp[i][j], min(dp[i - 1][j], dp[i][j - 1]) + 1);
         ckmax(ans, a[i][j] - dp[i][j]);
      }
   }

   reset();
   for (int i = 1; i <= n; i++) {
      for (int j = m; j >= 1; j--) {
         dp[i][j] = a[i][j] + 1;
         ckmin(dp[i][j], min(dp[i - 1][j], dp[i][j + 1]) + 1);
         ckmax(ans, a[i][j] - dp[i][j]);
      }
   }

   reset();
   for (int i = n; i >= 1; i--) {
      for (int j = 1; j <= m; j++) {
         dp[i][j] = a[i][j] + 1;
         ckmin(dp[i][j], min(dp[i + 1][j], dp[i][j - 1]) + 1);
         ckmax(ans, a[i][j] - dp[i][j]);
      }
   }

   reset();
   for (int i = n; i >= 1; i--) {
      for (int j = m; j >= 1; j--) {
         dp[i][j] = a[i][j] + 1;
         ckmin(dp[i][j], min(dp[i + 1][j], dp[i][j + 1]) + 1);
         ckmax(ans, a[i][j] - dp[i][j]);
      }
   }

   return ans;
}

signed main() {
#ifdef LOCAL
   freopen("input.txt", "r", stdin);
#endif
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   
   int t = 1;
//   cin >> t;

   while (t--) {
      read();
      cout << solve() << endl;
   }

   return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 1 ms 856 KB Output is correct
14 Correct 1 ms 1012 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 1 ms 860 KB Output is correct
16 Correct 1 ms 856 KB Output is correct
17 Correct 1 ms 1012 KB Output is correct
18 Correct 88 ms 16740 KB Output is correct
19 Correct 91 ms 16724 KB Output is correct
20 Correct 82 ms 16380 KB Output is correct
21 Correct 87 ms 16640 KB Output is correct
22 Correct 93 ms 16708 KB Output is correct
23 Correct 86 ms 16672 KB Output is correct
24 Correct 80 ms 17228 KB Output is correct