Submission #677442

#	Time	Username	Problem	Language	Result	Execution time	Memory
677442		LucaLucaM	Maxcomp (info1cup18_maxcomp)	C++17	0 / 100	1 ms	460 KiB

maxcomp

#include <bits/stdc++.h>

using namespace std;

int a[1001][1001];
int b[1001][1001];

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

/**
fie b[i][j] - cea mai apropiata poizitie a.i. a[b[i][j].first][b[i][j].second] > a[i][j]
calculam cu lee
**/

struct state
{
    int i, j, d, maxi, mini;
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

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

    queue<state>q;

    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            q.push({i, j, 0, a[i][j], a[i][j]});
            b[i][j] = -1;
        }
    }

    int ans = 0;

    while (!q.empty())
    {
        int i = q.front().i, j = q.front().j, d = q.front().d, maxim = q.front().maxi, minim = q.front().mini;
        q.pop();

        for (int k=0; k<4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x > 0 && y > 0 && x <= n && y <= m)
            {
                if (max(maxim, a[x][y]) - min(minim, a[x][y]) - (d + 1) > b[x][y])
                {
                    b[x][y] = max(maxim, a[x][y]) - min(minim, a[x][y]) - (d + 1);
                    ans = max(ans, b[x][y]);
                    q.push({x, y, max(maxim, a[x][y]), min(minim, a[x][y]), d + 1});
                }
            }
        }
    }

    cout << ans;

    return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40