oj.uz

Submission #197579

# Submission time Handle Problem Language Result Execution time Memory
197579 2020-01-21T19:35:04 Z GSmerch Maxcomp (info1cup18_maxcomp) C++14
100 / 100
 191 ms 52088 KB 
#include <bits/stdc++.h>

typedef long long ll;
typedef long double ld;


using namespace std;

#define fi first
#define se second
#define sz(x) (x).size()
#define pll pair<ll,ll >
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define endln '\n'
#define cont continue

const ll MaxN = 1e3 + 100;
const ll LogN = 20;
ll Inf = 1e18;
const ll dx[4] = { 0,1,0,-1 };
const ll dy[4] = { 1,0,-1,0 };

bool used[MaxN][MaxN];
ll Mt[MaxN][MaxN];
ll dp[4][MaxN][MaxN];

int main() {

#ifdef LOCAL
    ifstream cin("input.txt");
    ofstream cout("output.txt");
#else
    //ifstream cin("points.in");
    //ofstream cout("points.out");
#endif
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    ll N, M;
    cin>>N>>M;
    for(int i = 0;i<N;i++){
        for(int j =0;j<M;j++){
            cin>>Mt[i][j];
        }
    }
    dp[0][0][0] = -1;
    for(int i =0;i<N;i++){
        for(int j =0;j<M;j++){
            ll k = -1;
            if(j != 0) k = max(k, Mt[i][j] + dp[0][i][j-1] - Mt[i][j-1] -1);
            if(i != 0) k = max(k, Mt[i][j] + dp[0][i-1][j] - Mt[i-1][j] -1);
            dp[0][i][j] = k;
        }
    }
    dp[1][N-1][0] = -1;
    for(int i =N-1;i>=0;i--){
        for(int j =0;j<M;j++){
            ll k = -1;
            if(j != 0) k = max(k, Mt[i][j] + dp[1][i][j-1] - Mt[i][j-1] -1);
            if(i != N-1) k = max(k, Mt[i][j] + dp[1][i+1][j] - Mt[i+1][j] -1);
            dp[1][i][j] = k;
        }
    }
    dp[2][0][M-1] = -1;
    for(int i =0;i<N;i++){
        for(int j =M-1; j>= 0;j--){
            ll k = -1;
            if(j != M-1) k = max(k, Mt[i][j] + dp[2][i][j+1] - Mt[i][j+1] -1);
            if(i != 0) k = max(k, Mt[i][j] + dp[2][i-1][j] - Mt[i-1][j] -1);
            dp[2][i][j] = k;
        }
    }
    dp[3][N-1][M-1] = -1;
    for(int i =N-1;i>=0;i--){
        for(int j =M-1;j>=0;j--){
            ll k = -1;
            if(j != M-1) k = max(k, Mt[i][j] + dp[3][i][j+1] - Mt[i][j+1] -1);
            if(i != N-1) k = max(k, Mt[i][j] + dp[3][i+1][j] - Mt[i+1][j] -1);
            dp[3][i][j] = k;
        }
    }
    ll Ans = -1;
    for(int i =0;i<N;i++){
        for(int j =0;j<M;j++){
            for(int k =0;k<4;k++){
                Ans = max(Ans, dp[k][i][j]);
            }
        }
    }
    cout<<Ans;

    return 0;
}

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 376 KB Output is correct
3 Correct 1 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 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 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 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 376 KB Output is correct
3 Correct 1 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 1400 KB Output is correct
10 Correct 3 ms 1528 KB Output is correct
11 Correct 4 ms 1528 KB Output is correct
12 Correct 3 ms 1528 KB Output is correct
13 Correct 3 ms 1528 KB Output is correct
14 Correct 3 ms 1528 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 376 KB Output is correct
3 Correct 1 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 3 ms 1400 KB Output is correct
13 Correct 3 ms 1528 KB Output is correct
14 Correct 4 ms 1528 KB Output is correct
15 Correct 3 ms 1528 KB Output is correct
16 Correct 3 ms 1528 KB Output is correct
17 Correct 3 ms 1528 KB Output is correct
18 Correct 191 ms 51940 KB Output is correct
19 Correct 189 ms 51960 KB Output is correct
20 Correct 183 ms 51556 KB Output is correct
21 Correct 191 ms 51960 KB Output is correct
22 Correct 189 ms 52088 KB Output is correct
23 Correct 190 ms 51960 KB Output is correct
24 Correct 185 ms 50552 KB Output is correct