제출 #197579

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
197579		GSmerch	Maxcomp (info1cup18_maxcomp)	C++14	100 / 100	191 ms	52088 KiB

maxcomp

#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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40