oj.uz

Submission #197383

# Submission time Handle Problem Language Result Execution time Memory
197383 2020-01-20T16:49:40 Z kmekhovich Maxcomp (info1cup18_maxcomp) C++14
100 / 100
 275 ms 24772 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
#define pb push_back
#define fst first
#define snd second
#define all(c) (c).begin(), (c).end()
typedef long long ll;
typedef long double ld;
const ll INF64 = 1e18 + 228;
const int INF32 = 1e9 + 1337;
const int MOD = 1e9 + 7;
const ld eps = 1e-7;
const int N = 1e3 + 3;
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;
    vector< vector<ll> > a(n, vector<ll>(m));
    vector< vector<ll> > dp(n, vector<ll>(m, INF64));
    for(auto& it : a)
        for(auto& it2 : it)
            cin >> it2;
    ll ans = -INF64;
    for(int i = 0; i < n + m - 1; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            int x = j;
            int y = i - j;
            if(x >= n || y < 0 || y >= m) continue;
            dp[x][y] = min(dp[x][y], a[x][y] - x - y);
            if(x)
                dp[x][y] = min(dp[x][y], dp[x - 1][y]);
            if(y)
                dp[x][y] = min(dp[x][y], dp[x][y - 1]);
            ans = max(ans, a[x][y] - x - y - dp[x][y] - 1);
        }
    }
    dp.clear();
    dp.resize(n, vector<ll>(m, INF64));
    for(int i = n + m - 1; i >= 0; i--)
    {
        for(int j = 0; j <= i; j++)
        {
            int x = j;
            int y = i - j;
            if(x >= n || y < 0 || y >= m) continue;
            dp[x][y] = min(dp[x][y], a[x][y] - (n + m - 2 - (x + y)));
            if(x < n - 1)
                dp[x][y] = min(dp[x][y], dp[x + 1][y]);
            if(y < m - 1)
                dp[x][y] = min(dp[x][y], dp[x][y + 1]);
            ans = max(ans, a[x][y] - (n + m - 2 - (x + y)) - dp[x][y] - 1);
        }
    }
    dp.clear();
    dp.resize(n, vector<ll>(m, INF64));
    reverse(all(a));
    for(int i = 0; i < n + m - 1; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            int x = j;
            int y = i - j;
            if(x >= n || y < 0 || y >= m) continue;
            dp[x][y] = min(dp[x][y], a[x][y] - x - y);
            if(x)
                dp[x][y] = min(dp[x][y], dp[x - 1][y]);
            if(y)
                dp[x][y] = min(dp[x][y], dp[x][y - 1]);
            ans = max(ans, a[x][y] - x - y - dp[x][y] - 1);
        }
    }
    dp.clear();
    dp.resize(n, vector<ll>(m, INF64));
    for(int i = n + m - 1; i >= 0; i--)
    {
        for(int j = 0; j <= i; j++)
        {
            int x = j;
            int y = i - j;
            if(x >= n || y < 0 || y >= m) continue;
            dp[x][y] = min(dp[x][y], a[x][y] - (n + m - 2 - (x + y)));
            if(x < n - 1)
                dp[x][y] = min(dp[x][y], dp[x + 1][y]);
            if(y < m - 1)
                dp[x][y] = min(dp[x][y], dp[x][y + 1]);
            ans = max(ans, a[x][y] - (n + m - 2 - (x + y)) - dp[x][y] - 1);
        }
    }
    cout << ans;

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 269 ms 24772 KB Output is correct
19 Correct 275 ms 24676 KB Output is correct
20 Correct 256 ms 23676 KB Output is correct
21 Correct 268 ms 24632 KB Output is correct
22 Correct 271 ms 24632 KB Output is correct
23 Correct 270 ms 24612 KB Output is correct
24 Correct 258 ms 24608 KB Output is correct