oj.uz

Submission #46226

# Submission time Handle Problem Language Result Execution time Memory
46226 2018-04-18T07:24:55 Z grumpy_gordon Maxcomp (info1cup18_maxcomp) C++17
100 / 100
 166 ms 68608 KB 
/*
                     .:*+=%@@@@@@=-.
                 .:=@#@@@#@@#######%==*.
              .-=####@######%*-.....:%##%.
            .*@###########%+:--........-%@-
          .*@##############@+--.........-:%-
        .+##################@==%%%%=+*:----+.
      .-@####################%++%@@@@@=+**%@@*
      .%###################@%%@@@###@%+:--%@@%.
     -@###################@%%%%*::*%++:-----=@+.
    -#####################@%=++++++*:-------.-=:
   .+####################@%++*::-:::--::*:::***=:
   .@#####################%=++*::::-:::++*=##@@#@-
  ..#####################@%%=++**:::::**+%@#@%%##-..
   .%####################@@%=+++*+****::*=@######@.
  .=######################@%%==+==++**+=@%@##@###+:...
  -#######################@@@%%%===++=@@@%=++===*::--...
  -########################@@@@@@@%==%%=++==@@:::::*:--.
..:#########################@@@@@@%%======++++::-..:-.--...
%#############################@###@%%@@%==%=%*----.--.::---.
#############################################*-:*:-:---*---- .
#############################################*--*--:---*---:-.
#############################################+--::--::-*::-::.
###########################################+:*-.---.---.:---*-..
###########################################**:-----------------.
##########################################@::**:--::::::--:::::-
###########################################:--:*:::::::::**::*+*
###########################################=:::***::::::**:::*+*
############################@@@@@@#########@+****::::********+++
############################@%%%%%@@@@@@@###%+***::::::::***+==+
############################@%%%%%%%%%%%@####=+:::-::::-::*+=%%+
#############################@%%%%%%%%%%@#####=::--------:*=%@%+
%###########################@%%%%==%%%%%%@##@#=:------..-:+%@@%=
----------------------------------------------
--------------------------------------------
----------------------------------------------
--------------------------------------------
----------------------------------------------

         o###########oo
      o##"          ""##o
    o#"                "##
  o#"                    "#o
 #"  ##              ##   "##
#"                          ##
#  ###################       #
#                            #
#                            #
#                            #
#                            #
#                            #
#                            #
#o                           #
"#o                         ##
 "#o                       ##
  "#o                    o#"
   "#o                  ##
     "#o              o#"
       "#ooo      ooo#######oo
        ###############   "######o
     o###""        "###o      # ###
   o###o     oooo    ###    oo####"
 o###**#     #**#   ############"
 ""##""""""""""###########    #
    # oooooooo#"#**     ##    #
    # #       # # **    ##    #
    #o#       #o#  *****###ooo#
                        ##
                        ##   o###o
                        ## o##***##
               o########## #***#**##o
             o##"   ""###  #***##***#
 o#######o  ###   oo####   ##**####*#
o##"  ""#############""     ##****###
##"         ##              ##*##*###
##          ###              ##### ##
##           ###              # ##  #
##            ##                 #
##             ##
##             ###
##              ###oo
###              ""###
 ###
  ###
*/
#include <bits/stdc++.h>

//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
//float __attribute__((aligned(32)))

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

typedef unsigned int uint;

ll sqr(ll x){
    return x * x;
}

int mysqrt(ll x){
    int l = 0, r = 1e9 + 1;
    while (r - l > 1){
        int m = (l + r) / 2;
        if (m * (ll)m <= x)
            l = m;
        else
            r = m;
    }
    return l;
}

mt19937 rnd(1227);

mt19937_64 rndll(12365);

ll AR = 19, BR = 13, CR = 23, XR = 228, YR = 322, MODR = 1e9 + 993;

ll myrand(){
    ll ZR = (XR * AR + YR * BR + CR) % MODR;
    XR = YR;
    YR = ZR;
    return ZR;
}

const int Mod = 1e9 + 9;

int bpow(int x, int y){
    if (y == 0)
        return 1;
    if (y == 1)
        return x;
    int ret = bpow(x, y >> 1);
    ret = (ret * (ll)ret) % Mod;
    if (y & 1)
        ret = (ret * (ll)x) % Mod;
    return ret;
}

int bdiv(int x, int y){
    return (x * (ll)bpow(y, Mod - 2)) % Mod;
}

void setmin(int &x, int y){
    x = min(x, y);
}

void setmax(int &x, int y){
    x = max(x, y);
}

void setmin(ll &x, ll y){
    x = min(x, y);
}

void setmax(ll &x, ll y){
    x = max(x, y);
}

int gcd(int a, int b){
    return a ? gcd(b % a, a) : b;
}

const ll llinf = 2e18 + 100;

const double eps = 1e-9;

const int maxn = 2e5 + 100, maxw = 1e7 + 100, inf = 2e9 + 100, sq = 300, mod = 1e9 + 9, LG = 17;

int n, m;

int a[1000][1000];

int q[1000][1000];

int get(int i, int j){
    if (i >= 0 && j >= 0 && i < n && j < m)
        return q[i][j];
    return -inf;
}

int main()
{
    #ifdef ONPC
    //ifstream cin("a.in");
    //ofstream cout("a.out");
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    #else
    //ifstream cin("gymnasts.in");
    //ofstream cout("gymnasts.out");
    //freopen("sort.in", "r", stdin);
    //freopen("sort.out", "w", stdout);
    #endif // ONPC
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            q[i][j] = max(-a[i][j] + i + j, max(get(i - 1, j), get(i, j - 1))),
            setmax(ans, a[i][j] - i - j + q[i][j]);
    for (int i = n - 1; i >= 0; i--)
        for (int j = m - 1; j >= 0; j--)
            q[i][j] = max(-a[i][j] - i - j, max(get(i + 1, j), get(i, j + 1))),
            setmax(ans, a[i][j] + i + j + q[i][j]);
    for (int i = n - 1; i >= 0; i--)
        for (int j = 0; j < m; j++)
            q[i][j] = max(-a[i][j] - i + j, max(get(i + 1, j), get(i, j - 1))),
            setmax(ans, a[i][j] + i - j + q[i][j]);
    for (int i = 0; i < n; i++)
        for (int j = m - 1; j >= 0; j--)
            q[i][j] = max(-a[i][j] + i - j, max(get(i - 1, j), get(i, j + 1))),
            setmax(ans, a[i][j] - i + j + q[i][j]);
    cout << ans - 1;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 2 ms 736 KB Output is correct
6 Correct 2 ms 736 KB Output is correct
7 Correct 2 ms 736 KB Output is correct
8 Correct 2 ms 736 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 2 ms 792 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 2 ms 736 KB Output is correct
6 Correct 2 ms 736 KB Output is correct
7 Correct 2 ms 736 KB Output is correct
8 Correct 2 ms 736 KB Output is correct
9 Correct 2 ms 1184 KB Output is correct
10 Correct 2 ms 1260 KB Output is correct
11 Correct 2 ms 1260 KB Output is correct
12 Correct 3 ms 1268 KB Output is correct
13 Correct 2 ms 1292 KB Output is correct
14 Correct 2 ms 1316 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 2 ms 736 KB Output is correct
6 Correct 2 ms 736 KB Output is correct
7 Correct 2 ms 736 KB Output is correct
8 Correct 2 ms 736 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 2 ms 792 KB Output is correct
12 Correct 2 ms 1184 KB Output is correct
13 Correct 2 ms 1260 KB Output is correct
14 Correct 2 ms 1260 KB Output is correct
15 Correct 3 ms 1268 KB Output is correct
16 Correct 2 ms 1292 KB Output is correct
17 Correct 2 ms 1316 KB Output is correct
18 Correct 146 ms 17332 KB Output is correct
19 Correct 148 ms 26020 KB Output is correct
20 Correct 142 ms 34176 KB Output is correct
21 Correct 155 ms 42680 KB Output is correct
22 Correct 166 ms 51128 KB Output is correct
23 Correct 154 ms 59684 KB Output is correct
24 Correct 155 ms 68608 KB Output is correct