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 |
|
|
|
|
|
|
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 |