oj.uz

Submission #494703

# Submission time Handle Problem Language Result Execution time Memory
494703 2021-12-16T02:43:14 Z syl123456 Maxcomp (info1cup18_maxcomp) C++17
100 / 100
 176 ms 20688 KB 
#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wparentheses"
#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
#define random random_device rd; mt19937 rng(rd())
using namespace std;
template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
    return i << j.first << ' ' << j.second;
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
    i << '{' << j.size() << ':';
    for (T ii : j) i << ' ' << ii;
    return i << '}';
}
void Debug(bool _split) {}
template<typename T1, typename ...T2>
void Debug(bool _split, T1 x, T2 ...args) {
    if (_split)
        cerr << ", ";
    cerr << x, Debug(true, args...);
}
template<typename T>
void Debuga(T *i, int n) {
    cerr << '[';
    for (int j = 0; j < n; ++j) cerr << i[j] << " ]"[j == n - 1];
    cerr << endl;
}
#ifdef SYL
#define debug(args...) cerr << "Line(" << __LINE__ << ") -> [" << #args << "] is [", Debug(false, args), cerr << ']' << endl
#define debuga(i) cerr << "Line(" << __LINE__ << ") -> [" << #i << "] is ", Debuga(i, sizeof(i) / sizeof(typeid(*i).name()))
#else
#define debug(args...) void(0)
#define debuga(i) void(0)
#endif
typedef long long ll;
typedef pair<int, int> pi;
const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    int a[n][m];
    ll dp[n][m], ans = -1;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> a[i][j];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            dp[i][j] = a[i][j];
            if (i)
                dp[i][j] = max(dp[i][j], dp[i - 1][j] - 1);
            if (j)
                dp[i][j] = max(dp[i][j], dp[i][j - 1] - 1);
            ans = max(ans, dp[i][j] - a[i][j] - 1);
        }
    for (int i = 0; i < n; ++i)
        for (int j = m - 1; ~j; --j) {
            dp[i][j] = a[i][j];
            if (i)
                dp[i][j] = max(dp[i][j], dp[i - 1][j] - 1);
            if (j + 1 < m)
                dp[i][j] = max(dp[i][j], dp[i][j + 1] - 1);
            ans = max(ans, dp[i][j] - a[i][j] - 1);
        }
    for (int i = n - 1; ~i; --i)
        for (int j = 0; j < m; ++j) {
            dp[i][j] = a[i][j];
            if (i + 1 < n)
                dp[i][j] = max(dp[i][j], dp[i + 1][j] - 1);
            if (j)
                dp[i][j] = max(dp[i][j], dp[i][j - 1] - 1);
            ans = max(ans, dp[i][j] - a[i][j] - 1);
        }
    for (int i = n - 1; ~i; --i)
        for (int j = m - 1; ~j; --j) {
            dp[i][j] = a[i][j];
            if (i + 1 < n)
                dp[i][j] = max(dp[i][j], dp[i + 1][j] - 1);
            if (j + 1 < m)
                dp[i][j] = max(dp[i][j], dp[i][j + 1] - 1);
            ans = max(ans, dp[i][j] - a[i][j] - 1);
        }
    cout << ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 416 KB Output is correct
2 Correct 1 ms 220 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 216 KB Output is correct
8 Correct 1 ms 216 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 220 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 416 KB Output is correct
2 Correct 1 ms 220 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 216 KB Output is correct
8 Correct 1 ms 216 KB Output is correct
9 Correct 1 ms 372 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 376 KB Output is correct
14 Correct 1 ms 364 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 416 KB Output is correct
2 Correct 1 ms 220 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 216 KB Output is correct
8 Correct 1 ms 216 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 220 KB Output is correct
12 Correct 1 ms 372 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 376 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 165 ms 20316 KB Output is correct
19 Correct 154 ms 20612 KB Output is correct
20 Correct 154 ms 19620 KB Output is correct
21 Correct 175 ms 20468 KB Output is correct
22 Correct 176 ms 20340 KB Output is correct
23 Correct 162 ms 20292 KB Output is correct
24 Correct 166 ms 20688 KB Output is correct