Submission #47241

#	Time	Username	Problem	Language	Result	Execution time	Memory
47241		PowerOfNinjaGo	Maxcomp (info1cup18_maxcomp)	C++17	100 / 100	258 ms	68072 KiB

maxcomp

//Power Of Ninja Go
#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector< ii > vii;
#define X first
#define Y second
#define pb push_back
const int maxn = 1e3+5;
int arr[maxn][maxn];
int tmp[maxn][maxn];
ll mn[maxn][maxn];
ll best = -1e18;
int n, m;
void swap()
{
    for(int i = 1; i<= n; i++)
    {
        for(int j = 1; j<= m; j++)
        {
            tmp[m-j+1][i] = arr[i][j];
        }
    }
    swap(m, n);
    for(int i = 1; i<= n; i++)
    {
        for(int j = 1; j<= m; j++)
        {
            arr[i][j] = tmp[i][j];
        }
    }
}
void solve()
{
    for(int i = 1; i<= n; i++)
    {
        for(int j = 1; j<= m; j++)
        {
            ll here = arr[i][j]-i-j;
            ll choice = 1e18;
            if(i> 1) choice = min(choice, mn[i-1][j]);
            if(j> 1) choice = min(choice, mn[i][j-1]);
            best = max(best, here-choice-1);
            mn[i][j] = here;
            if(i> 1) mn[i][j] = min(mn[i-1][j], mn[i][j]);
            if(j> 1) mn[i][j] = min(mn[i][j-1], mn[i][j]);
            //cout << mn[i][j] << ' ';
        }
        //cout << endl;
    }
}
int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i<= n; i++)
    {
        for(int j = 1; j<= m; j++)
        {
            scanf("%d", arr[i]+j);
        }
    }
    solve();
    swap(); solve();
    swap(); solve();
    swap(); solve();
    cout << best << endl;
}

Compilation message (stderr)

maxcomp.cpp: In function 'int main()':
maxcomp.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
maxcomp.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", arr[i]+j);
             ~~~~~^~~~~~~~~~~~~~~~

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