oj.uz

Submission #1069958

# Submission time Handle Problem Language Result Execution time Memory
1069958 2024-08-22T10:38:09 Z Ice_man Maxcomp (info1cup18_maxcomp) C++14
100 / 100
 93 ms 17588 KB 
/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include <iostream>
#include <chrono>
#include <vector>

///#include "grader.h"

#define maxn 1005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")

using namespace std;


typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef long long ll;
typedef pair <ll, ll> pll;
typedef pair <int, ll> pil;
typedef pair <ll, int> pli;
typedef long double pd;


int n, m;
int a[maxn][maxn];

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


int dp[maxn][maxn];
int ans = -INF;

void _try()
{
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            dp[i][j] = a[i][j];

            if(i > 1)
                dp[i][j] = max(dp[i][j], dp[i - 1][j] - 1);
            if(j > 1)
                dp[i][j] = max(dp[i][j], dp[i][j - 1] - 1);

            ans = max(ans, dp[i][j] - a[i][j] - 1);
        }
}


void solve()
{
    ans = -INF;

    _try();

    for(int i = 1; i <= n / 2; i++)
        for(int j = 1; j <= m; j++)
            swap(a[i][j] , a[n - i + 1][j]);

    /**cout << "-------------------------" << endl;
    for(int i = 1; i <= n; i++ , cout << endl)
        for(int j = 1; j <= m; j++)
            cout << a[i][j] << " ";*/
    _try();

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m / 2; j++)
            swap(a[i][j] , a[i][m - j + 1]);

    /**cout << "-------------------------" << endl;
    for(int i = 1; i <= n; i++ , cout << endl)
        for(int j = 1; j <= m; j++)
            cout << a[i][j] << " ";*/

    _try();

    for(int i = 1; i <= n / 2; i++)
        for(int j = 1; j <= m; j++)
            swap(a[i][j] , a[n - i + 1][j]);

    /**cout << "-------------------------" << endl;
    for(int i = 1; i <= n; i++ , cout << endl)
        for(int j = 1; j <= m; j++)
            cout << a[i][j] << " ";*/

    _try();

    cout << ans << endl;
}




int main()
{

    /**#ifdef ONLINE_JUDGE /// promeni
        freopen("taxi.in", "r", stdin);
        freopen("taxi.out", "w", stdout);
    #endif*/

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ///startT = std::chrono::high_resolution_clock::now();


    read();
    solve();


    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 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 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 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 1 ms 4700 KB Output is correct
13 Correct 1 ms 4700 KB Output is correct
14 Correct 1 ms 4700 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 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 4700 KB Output is correct
13 Correct 1 ms 4700 KB Output is correct
14 Correct 1 ms 4700 KB Output is correct
15 Correct 1 ms 4700 KB Output is correct
16 Correct 1 ms 4700 KB Output is correct
17 Correct 1 ms 4700 KB Output is correct
18 Correct 85 ms 16696 KB Output is correct
19 Correct 86 ms 16824 KB Output is correct
20 Correct 79 ms 16468 KB Output is correct
21 Correct 80 ms 16836 KB Output is correct
22 Correct 88 ms 16720 KB Output is correct
23 Correct 85 ms 16708 KB Output is correct
24 Correct 93 ms 17588 KB Output is correct