Submission #44744

#	Time	Username	Problem	Language	Result	Execution time	Memory
44744		model_code	Maxcomp (info1cup18_maxcomp)	C++17	100 / 100	236 ms	4536 KiB

maxcomp

#include <bits/stdc++.h>

using namespace std;

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

int a, b, n, m, best_so_far_con, best_so_far_exp, no_of_operations, no_of_touched, min_comp, max_comp;
int mat[N][N], l[N], used[N][N] , on[N][N];

void readData()
{
    //freopen("maxComp.in" , "r" , stdin);
    //freopen("maxComp.out" , "w" , stdout);
    scanf("%d" , &n);
    scanf("%d" , &m);

    assert(1 <= n && n <= 1000 && 1 <= m && m <= 1000);
    for (int i = 0 ; i < n ; ++i)
        for (int j = 0 ; j < m ; ++j)
        {
            scanf("%d" , &mat[i][j]);
            assert(0 <= mat[i][j] && mat[i][j] <= 1000000000);
        }
}

int getValue()
{
    int ret = -1;
    for (int i = 0 ; i < n ; ++i)
    {
        for (int j = 0 ; j < m ; ++j)
            if (i > 0)
            {
                if (j > 0)
                    l[j] = min(min(l[j] , l[j - 1]) , mat[i][j] - i - j);
                else l[j] = min(l[j] , mat[i][j] - i - j);
            }
            else
            {
                if (j > 0)
                    l[j] = min(l[j - 1] , mat[i][j] - i - j);
                else l[j] = mat[i][j] - i - j;
            }

        for (int j = 0 ; j < m ; ++j)
            ret = max(ret , mat[i][j] - i - j - l[j] - 1);
    }

    return ret;
}

void solverNM()
{
    int best_so_far = getValue();

    for (int i = 0 ; i < n ; ++i)
        for (int j = 0 ; j < m / 2 ; ++j)
            swap(mat[i][j] , mat[i][m - 1 - j]);
    best_so_far = max(best_so_far , getValue());

    for (int i = 0 ; i < n / 2 ; ++i)
        for (int j = 0 ; j < m ; ++j)
            swap(mat[n - 1 - i][j] , mat[i][j]);
    best_so_far = max(best_so_far , getValue());

    for (int i = 0 ; i < n ; ++i)
        for (int j = 0 ; j < m / 2 ; ++j)
            swap(mat[i][j] , mat[i][m - 1 - j]);
    best_so_far = max(best_so_far , getValue());

    printf("%d\n" , best_so_far);
}

int abval(int x)
{
    if (x < 0) return -x;
    return x;
}

void solverNNMM()
{
    int best_so_far = -1;
    for (int i = 0 ; i < n ; ++i)
        for (int j = 0 ; j < m ; ++j)
            for (int x = 0 ; x < n ; ++x)
                for (int y = 0 ; y < m ; ++y)
                {
                    int k = mat[x][y] - mat[i][j] - abval(x - i) - abval(y - j) - 1;
                    best_so_far = max(best_so_far , k);
                }

    printf("%d\n" , best_so_far);
}

void go(int i , int j , int a , int b , int cnt , int limit)
{
    if (cnt > limit) return;
    no_of_operations++;
    best_so_far_con = max(best_so_far_con , b-a-cnt);
    for (int p = 0 ; p < 4 ; ++p)
    if (0 <= i + dx[p] && i + dx[p] < n && 0 <= j + dy[p] && j + dy[p] < m && !used[i + dx[p]][j + dy[p]])
    {
        used[i + dx[p]][j + dy[p]] = 1;
        go(i + dx[p] , j + dy[p] , min(a , mat[i + dx[p]][j + dy[p]]) , max(b , mat[i + dx[p]][j + dy[p]]) , cnt+1 , limit);
        used[i + dx[p]][j + dy[p]] = 0;
    }
}

void solverconNM(int limit)
{
    best_so_far_con = -1;
    for (int i = 0 ; i < n ; ++i)
        for (int j = 0 ; j < m ; ++j)
        {
            used[i][j] = 1;
            go(i , j , mat[i][j] , mat[i][j] , 1 , limit);
            used[i][j] = 0;
        }
    printf("%d\n" , best_so_far_con);
    //printf("No of operations : %d\n", no_of_operations);
}

void check(int i , int j)
{
    no_of_touched++;
    min_comp = min(min_comp , mat[i][j]);
    max_comp = max(max_comp , mat[i][j]);
    for (int p = 0 ; p < 4 ; ++p)
    if (0 <= i + dx[p] && i + dx[p] < n && 0 <= j + dy[p] && j + dy[p] < m && on[i + dx[p]][j + dy[p]] && !used[i + dx[p]][j + dy[p]])
    {
        used[i + dx[p]][j + dy[p]] = 1;
        check(i + dx[p] , j + dy[p]);
    }
}

void solverexpNM()
{
    best_so_far_exp = -1;
    for (int mask = 1 ; mask < (1 << (n * m)) ; ++mask)
    {
        int cnt = 0;
        for (int i = 0 ; i < n ; ++i)
            for (int j = 0 ; j < m ; ++j)
            {
                used[i][j] = 0;
                if (mask & (1 << (i * m + j)))
                {
                    cnt++;
                    a = i, b = j;
                    on[i][j] = 1;
                }
                else on[i][j] = 0;
            }

        no_of_touched = 0;
        min_comp = mat[a][b];
        max_comp = mat[a][b];
        used[a][b] = 1;
        check(a , b);

        if (no_of_touched == cnt)
        best_so_far_exp = max(best_so_far_exp , max_comp-min_comp-cnt);
    }
    printf("%d\n", best_so_far_exp);
}

int main()
{

readData();
solverNM();
//solverNNMM();
//solverconNM(20);
//solverexpNM();

return 0;
}

Compilation message (stderr)

maxcomp.cpp: In function 'void readData()':
maxcomp.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d" , &n);
     ~~~~~^~~~~~~~~~~
maxcomp.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d" , &m);
     ~~~~~^~~~~~~~~~~
maxcomp.cpp:23:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d" , &mat[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~~

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