oj.uz

Submission #866473

# Submission time Handle Problem Language Result Execution time Memory
866473 2023-10-26T08:28:15 Z aykhn Maxcomp (info1cup18_maxcomp) C++17
100 / 100
 272 ms 49188 KB 
#include <bits/stdc++.h>
 
// author : aykhn
 
using namespace std;
typedef long long ll;
 
#define pb push_back
#define ins insert
#define mpr make_pair
#define all(v) v.begin(), v.end()
#define bpc __builtin_popcount
#define bpcll __builtin_popcountll
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define int ll
#define infll 0x3F3F3F3F3F3F3F3F
#define inf 0x3F3F3F3F

const int MXN = 1e3 + 5;

int n, m;
int mat[MXN][MXN];
int ul[MXN][MXN], ur[MXN][MXN], dl[MXN][MXN], dr[MXN][MXN];

signed main()
{
    cin >> n >> m;
    for (int i = 0; i < MXN; i++)
    {
        for (int j = 0; j < MXN; j++)
        {
            mat[i][j] = ul[i][j] = ur[i][j] = dl[i][j] = dr[i][j] = inf;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> mat[i][j];
            int i1 = n - i + 1;
            int j1 = m - j + 1;
            ul[i][j] = mat[i][j] - (i + j - 2);
            ur[i][j] = mat[i][j] - (i + j1 - 2);
            dl[i][j] = mat[i][j] - (i1 + j - 2);
            dr[i][j] = mat[i][j] - (i1 + j1 - 2);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            ul[i][j] = min({ul[i - 1][j], ul[i][j - 1], ul[i][j]});
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = m; j >= 1; j--)
        {
            ur[i][j] = min({ur[i - 1][j], ur[i][j + 1], ur[i][j]});
        }
    }
    for (int i = n; i >= 1; i--)
    {
        for (int j = 1; j <= m; j++)
        {
            dl[i][j] = min({dl[i + 1][j], dl[i][j - 1], dl[i][j]});
        }
    }
    for (int i = n; i >= 1; i--)
    {
        for (int j = m; j >= 1; j--)
        {
            dr[i][j] = min({dr[i + 1][j], dr[i][j + 1], dr[i][j]});
        }
    }
    int ans = -inf;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            int i1 = n - i + 1;
            int j1 = m - j + 1;
            int mn = min({ul[i][j] + (i + j - 2), ur[i][j] + (i + j1 - 2), dl[i][j] + (i1 + j - 2), dr[i][j] + (i1 + j1 - 2)});
            mn++;
            ans = max(ans, mat[i][j] - mn);
        }
    }
    cout << ans << '\n';

}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 39772 KB Output is correct
2 Correct 6 ms 39772 KB Output is correct
3 Correct 6 ms 39872 KB Output is correct
4 Correct 6 ms 39868 KB Output is correct
5 Correct 6 ms 39772 KB Output is correct
6 Correct 7 ms 39772 KB Output is correct
7 Correct 6 ms 39772 KB Output is correct
8 Correct 6 ms 39768 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 39772 KB Output is correct
2 Correct 6 ms 39772 KB Output is correct
3 Correct 6 ms 39840 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 39772 KB Output is correct
2 Correct 6 ms 39772 KB Output is correct
3 Correct 6 ms 39872 KB Output is correct
4 Correct 6 ms 39868 KB Output is correct
5 Correct 6 ms 39772 KB Output is correct
6 Correct 7 ms 39772 KB Output is correct
7 Correct 6 ms 39772 KB Output is correct
8 Correct 6 ms 39768 KB Output is correct
9 Correct 8 ms 39772 KB Output is correct
10 Correct 7 ms 39772 KB Output is correct
11 Correct 6 ms 39844 KB Output is correct
12 Correct 7 ms 39772 KB Output is correct
13 Correct 8 ms 40028 KB Output is correct
14 Correct 7 ms 39772 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 39772 KB Output is correct
2 Correct 6 ms 39772 KB Output is correct
3 Correct 6 ms 39872 KB Output is correct
4 Correct 6 ms 39868 KB Output is correct
5 Correct 6 ms 39772 KB Output is correct
6 Correct 7 ms 39772 KB Output is correct
7 Correct 6 ms 39772 KB Output is correct
8 Correct 6 ms 39768 KB Output is correct
9 Correct 7 ms 39772 KB Output is correct
10 Correct 6 ms 39772 KB Output is correct
11 Correct 6 ms 39840 KB Output is correct
12 Correct 8 ms 39772 KB Output is correct
13 Correct 7 ms 39772 KB Output is correct
14 Correct 6 ms 39844 KB Output is correct
15 Correct 7 ms 39772 KB Output is correct
16 Correct 8 ms 40028 KB Output is correct
17 Correct 7 ms 39772 KB Output is correct
18 Correct 260 ms 48264 KB Output is correct
19 Correct 261 ms 48464 KB Output is correct
20 Correct 249 ms 47952 KB Output is correct
21 Correct 268 ms 48264 KB Output is correct
22 Correct 267 ms 48604 KB Output is correct
23 Correct 258 ms 48468 KB Output is correct
24 Correct 272 ms 49188 KB Output is correct