oj.uz

Submission #47241

# Submission time Handle Problem Language Result Execution time Memory
47241 2018-04-29T13:32:09 Z PowerOfNinjaGo Maxcomp (info1cup18_maxcomp) C++17
100 / 100
 258 ms 68072 KB 
//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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 556 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 760 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12396 KB Output is correct
2 Correct 9 ms 12524 KB Output is correct
3 Correct 9 ms 12524 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 556 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 3 ms 12524 KB Output is correct
10 Correct 3 ms 12524 KB Output is correct
11 Correct 3 ms 12524 KB Output is correct
12 Correct 3 ms 12524 KB Output is correct
13 Correct 3 ms 12524 KB Output is correct
14 Correct 3 ms 12524 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 556 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 9 ms 12396 KB Output is correct
10 Correct 9 ms 12524 KB Output is correct
11 Correct 9 ms 12524 KB Output is correct
12 Correct 3 ms 12524 KB Output is correct
13 Correct 3 ms 12524 KB Output is correct
14 Correct 3 ms 12524 KB Output is correct
15 Correct 3 ms 12524 KB Output is correct
16 Correct 3 ms 12524 KB Output is correct
17 Correct 3 ms 12524 KB Output is correct
18 Correct 243 ms 16368 KB Output is correct
19 Correct 245 ms 24948 KB Output is correct
20 Correct 224 ms 33288 KB Output is correct
21 Correct 230 ms 41676 KB Output is correct
22 Correct 258 ms 50472 KB Output is correct
23 Correct 214 ms 58780 KB Output is correct
24 Correct 177 ms 68072 KB Output is correct