Submission #1594108
Source Code Expand
#include "bits/stdc++.h" using namespace std; const int N = 205; int n, m; int arr[N][N]; int dp[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 = (a1 + b1) - (a2); if (dp[a1][b1][a2] != -1) { return dp[a1][b1][a2]; } 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] = 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)); } } } return dp[a1][b1][a2] = 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) << endl; }
Submission Info
Submission Time | |
---|---|
Task | D - Souvenirs |
User | rekt_n00b |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 1392 Byte |
Status | AC |
Exec Time | 191 ms |
Memory | 34048 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | Subtask4 | Subtask5 | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 50 / 50 | 80 / 80 | 120 / 120 | 150 / 150 | 200 / 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 | 10 ms | 33920 KB |
sample_2.txt | AC | 10 ms | 33920 KB |
sub1_in1.txt | AC | 10 ms | 33920 KB |
sub1_in2.txt | AC | 10 ms | 33920 KB |
sub1_in3.txt | AC | 10 ms | 33920 KB |
sub1_in4.txt | AC | 10 ms | 33920 KB |
sub2_in1.txt | AC | 10 ms | 33920 KB |
sub2_in2.txt | AC | 10 ms | 33920 KB |
sub2_in3.txt | AC | 10 ms | 33920 KB |
sub2_in4.txt | AC | 10 ms | 33920 KB |
sub3_in1.txt | AC | 9 ms | 33920 KB |
sub3_in2.txt | AC | 10 ms | 33920 KB |
sub3_in3.txt | AC | 10 ms | 33920 KB |
sub3_in4.txt | AC | 10 ms | 33920 KB |
sub4_in1.txt | AC | 10 ms | 33920 KB |
sub4_in2.txt | AC | 10 ms | 33920 KB |
sub4_in3.txt | AC | 11 ms | 33920 KB |
sub4_in4.txt | AC | 11 ms | 33920 KB |
sub5_in1.txt | AC | 13 ms | 33920 KB |
sub5_in2.txt | AC | 34 ms | 34048 KB |
sub5_in3.txt | AC | 191 ms | 34048 KB |
sub5_in4.txt | AC | 188 ms | 34048 KB |