Submission #1069958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069958		Ice_man	Maxcomp (info1cup18_maxcomp)	C++14	100 / 100	93 ms	17588 KiB

maxcomp

/**
 ____    ____    ____    __________________    ____    ____    ____
||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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40