Submission #1594107


Source Code Expand

#include "bits/stdc++.h"
using namespace std;

const int N = 50;

int n, m;
int arr[N][N];
int dp[N][N][N][N];

int dx[] = {0, 1};
int dy[] = {1, 0};

inline bool isValid(int x, int y) {
    return (0 <= x && x < n && 0 <= y && y < m);
}

inline int solve(int a1, int b1, int a2, int b2) {
    if (dp[a1][b1][a2][b2] != -1) {
        return dp[a1][b1][a2][b2];
    }
    if ((a1 == a2) && (b1 == b2)) {
        if ((a1 + b1 > 0) && (a1 + b1 < n + m - 2)) {
            return 0;
        }
    }
    if (a1 == n - 1 && b1 == m - 1) {
        return dp[a1][b1][a2][b2] = arr[a1][b1];
    }
    int score = arr[a1][b1];
    if (a1 != a2 || b1 != b2) {
        score += arr[a2][b2];
    }
    int result = 0;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            int na1 = a1 + dx[i];
            int nb1 = b1 + dy[i];
            int na2 = a2 + dx[j];
            int nb2 = b2 + dy[j];
            if (isValid(na1, nb1) && isValid(na2, nb2)) {
                result = max(result, solve(na1, nb1, na2, nb2));
            }
        }
    }
    return dp[a1][b1][a2][b2] = result + score;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
        }
    }
    memset(dp, -1, sizeof dp);
    cout << solve(0, 0, 0, 0) << endl;
}

Submission Info

Submission Time
Task D - Souvenirs
User rekt_n00b
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1394 Byte
Status RE
Exec Time 113 ms
Memory 24704 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3 Subtask4 Subtask5
Score / Max Score 0 / 0 50 / 50 80 / 80 120 / 120 150 / 150 0 / 200
Status
AC × 2
AC × 4
AC × 9
AC × 14
AC × 18
AC × 19
RE × 3
Set Name Test Cases
Sample sample_1.txt, sample_2.txt
Subtask1 sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub1_in4.txt
Subtask2 sample_1.txt, sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub1_in4.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub2_in4.txt
Subtask3 sample_1.txt, sample_2.txt, sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub1_in4.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub2_in4.txt, sub3_in1.txt, sub3_in2.txt, sub3_in3.txt, sub3_in4.txt
Subtask4 sample_1.txt, sample_2.txt, sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub1_in4.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub2_in4.txt, sub3_in1.txt, sub3_in2.txt, sub3_in3.txt, sub3_in4.txt, sub4_in1.txt, sub4_in2.txt, sub4_in3.txt, sub4_in4.txt
Subtask5 sample_1.txt, sample_2.txt, sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub1_in4.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub2_in4.txt, sub3_in1.txt, sub3_in2.txt, sub3_in3.txt, sub3_in4.txt, sub4_in1.txt, sub4_in2.txt, sub4_in3.txt, sub4_in4.txt, sub5_in1.txt, sub5_in2.txt, sub5_in3.txt, sub5_in4.txt
Case Name Status Exec Time Memory
sample_1.txt AC 8 ms 24704 KB
sample_2.txt AC 8 ms 24704 KB
sub1_in1.txt AC 8 ms 24704 KB
sub1_in2.txt AC 8 ms 24704 KB
sub1_in3.txt AC 8 ms 24704 KB
sub1_in4.txt AC 8 ms 24704 KB
sub2_in1.txt AC 8 ms 24704 KB
sub2_in2.txt AC 8 ms 24704 KB
sub2_in3.txt AC 8 ms 24704 KB
sub2_in4.txt AC 8 ms 24704 KB
sub3_in1.txt AC 8 ms 24704 KB
sub3_in2.txt AC 8 ms 24704 KB
sub3_in3.txt AC 8 ms 24704 KB
sub3_in4.txt AC 8 ms 24704 KB
sub4_in1.txt AC 8 ms 24704 KB
sub4_in2.txt AC 8 ms 24704 KB
sub4_in3.txt AC 9 ms 24704 KB
sub4_in4.txt AC 9 ms 24704 KB
sub5_in1.txt AC 12 ms 24704 KB
sub5_in2.txt RE 113 ms 256 KB
sub5_in3.txt RE 99 ms 256 KB
sub5_in4.txt RE 98 ms 256 KB