oj.uz

Submission #148119

# Submission time Handle Problem Language Result Execution time Memory
148119 2019-08-31T14:03:09 Z WhipppedCream Maxcomp (info1cup18_maxcomp) C++17
100 / 100
 217 ms 25388 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 380 KB Output is correct
2 Correct 2 ms 396 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12152 KB Output is correct
2 Correct 11 ms 12152 KB Output is correct
3 Correct 11 ms 12152 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 396 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 888 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 3 ms 888 KB Output is correct
12 Correct 3 ms 888 KB Output is correct
13 Correct 3 ms 1016 KB Output is correct
14 Correct 3 ms 920 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 396 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 11 ms 12152 KB Output is correct
10 Correct 11 ms 12152 KB Output is correct
11 Correct 11 ms 12152 KB Output is correct
12 Correct 3 ms 888 KB Output is correct
13 Correct 3 ms 1016 KB Output is correct
14 Correct 3 ms 888 KB Output is correct
15 Correct 3 ms 888 KB Output is correct
16 Correct 3 ms 1016 KB Output is correct
17 Correct 3 ms 920 KB Output is correct
18 Correct 217 ms 24676 KB Output is correct
19 Correct 211 ms 24568 KB Output is correct
20 Correct 200 ms 24312 KB Output is correct
21 Correct 208 ms 24568 KB Output is correct
22 Correct 212 ms 24700 KB Output is correct
23 Correct 215 ms 24568 KB Output is correct
24 Correct 180 ms 25388 KB Output is correct