9692022-02-06 18:29:39nmarciTáblatöréscpp11Accepted 50/5046ms24260 KiB
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <algorithm>
#include <list>
using namespace std;
using ll = long long int;

ll inf = 1e9+7;

int t[50][50] = {0};
int sum[50][50] = {0};
int dp[50][50][50][50][2] = {0};
bool done[50][50][50][50] = {false};
int n, m;

int sumarea(int x1, int y1, int x2,int y2){
    return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1-  1][y1 - 1];
}

void f(int x1, int y1,int x2,int y2){
    //cerr << x1 << " " << y1 << " " << x2 << " " << y2 << endl; 
    if(done[x1][y1][x2][y2]){
        return;
    }
    done[x1][y1][x2][y2] = true;
    if(x2 != x1 && y1 != y2){
        f(x1 + 1, y1, x2, y2);
        f(x1,y1,x2 - 1, y2);
        if(dp[x1][y1][x2][y2][0] < dp[x1 + 1][y1][x2][y2][1] + sumarea(x1,y1,x1, y2)){
            dp[x1][y1][x2][y2][0] = dp[x1 + 1][y1][x2][y2][1] + sumarea(x1,y1,x1, y2);
            dp[x1][y1][x2][y2][1] = dp[x1 + 1][y1][x2][y2][0];
        }
        if(dp[x1][y1][x2][y2][0] < dp[x1][y1][x2 - 1][y2][1] + sumarea(x2,y1,x2, y2)){
            dp[x1][y1][x2][y2][0] = dp[x1][y1][x2 - 1][y2][1] + sumarea(x2,y1,x2, y2);
            dp[x1][y1][x2][y2][1] = dp[x1][y1][x2 - 1][y2][0];
        }
    
        f(x1, y1 + 1, x2, y2);
        f(x1,y1,x2, y2 - 1);
        if(dp[x1][y1][x2][y2][0] < dp[x1][y1 + 1][x2][y2][1] + sumarea(x1,y1,x2, y1)){
            dp[x1][y1][x2][y2][0] = dp[x1][y1 + 1][x2][y2][1] + sumarea(x1,y1,x2, y1);
            dp[x1][y1][x2][y2][1] = dp[x1][y1 + 1][x2][y2][0];
        }
        if(dp[x1][y1][x2][y2][0] < dp[x1][y1][x2][y2 - 1][1] + sumarea(x1,y2,x2, y2)){
            dp[x1][y1][x2][y2][0] = dp[x1][y1][x2][y2 - 1][1] + sumarea(x1,y2,x2, y2);
            dp[x1][y1][x2][y2][1] = dp[x1][y1][x2][y2 - 1][0];
        }
    }
    else{
        dp[x1][y1][x2][y2][0] = sumarea(x1,y1,x2,y2);
    }
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            cin >> t[i][j];
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + t[i][j];
        }
    }
    f(1,1,n,m);
    cout << dp[1][1][n][m][0];
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/02ms2240 KiB
2Accepted0/027ms21016 KiB
3Accepted2/21ms2292 KiB
4Accepted2/22ms2396 KiB
5Accepted1/11ms2080 KiB
6Accepted1/13ms3704 KiB
7Accepted1/11ms2120 KiB
8Accepted2/23ms4072 KiB
9Accepted3/34ms4648 KiB
10Accepted3/38ms9056 KiB
11Accepted3/317ms14556 KiB
12Accepted3/314ms14528 KiB
13Accepted4/446ms21060 KiB
14Accepted4/427ms21116 KiB
15Accepted4/425ms24248 KiB
16Accepted5/526ms24260 KiB
17Accepted5/527ms24252 KiB
18Accepted5/528ms24232 KiB
19Accepted1/126ms24244 KiB
20Accepted1/126ms24212 KiB