Submission #1482232
Source Code Expand
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll
template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
int a[205][205], dp[205][205][205];
int h, w;
int func(int sx, int sy, int ex, int ey) {
if(sx >= w || ex >= w || sy >= h || ey >= h) return -INF;
if(dp[sx][sy][ex] != -1) return dp[sx][sy][ex];
int res = 0;
res = max(res, func(sx, sy+1, ex+1, ey));
res = max(res, func(sx, sy+1, ex, ey+1));
res = max(res, func(sx+1, sy, ex+1, ey));
res = max(res, func(sx+1, sy, ex, ey+1));
if(sx == ex && sy == ey) res += a[sy][sx];
else res += a[sy][sx] + a[ey][ex];
// cout << sx << " " << sy << " " << ex << " " << ey << endl;
// cout << res << endl;
return dp[sx][sy][ex] = res;
}
signed main(void)
{
cin >> h >> w;
REP(i, h) REP(j, w) cin >> a[i][j];
REP(i, 205) REP(j, 205) REP(k, 205) dp[i][j][k] = -1;
cout << func(0, 0, 0, 0) << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Souvenirs |
User |
ferin_tech |
Language |
C++14 (GCC 5.4.1) |
Score |
600 |
Code Size |
1568 Byte |
Status |
AC |
Exec Time |
171 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 |
12 ms |
33920 KB |
sample_2.txt |
AC |
12 ms |
33920 KB |
sub1_in1.txt |
AC |
12 ms |
33920 KB |
sub1_in2.txt |
AC |
12 ms |
33920 KB |
sub1_in3.txt |
AC |
12 ms |
33920 KB |
sub1_in4.txt |
AC |
12 ms |
33920 KB |
sub2_in1.txt |
AC |
11 ms |
33920 KB |
sub2_in2.txt |
AC |
12 ms |
33920 KB |
sub2_in3.txt |
AC |
12 ms |
33920 KB |
sub2_in4.txt |
AC |
12 ms |
33920 KB |
sub3_in1.txt |
AC |
12 ms |
33920 KB |
sub3_in2.txt |
AC |
12 ms |
33920 KB |
sub3_in3.txt |
AC |
12 ms |
33920 KB |
sub3_in4.txt |
AC |
12 ms |
33920 KB |
sub4_in1.txt |
AC |
12 ms |
33920 KB |
sub4_in2.txt |
AC |
12 ms |
33920 KB |
sub4_in3.txt |
AC |
12 ms |
33920 KB |
sub4_in4.txt |
AC |
13 ms |
33920 KB |
sub5_in1.txt |
AC |
15 ms |
33920 KB |
sub5_in2.txt |
AC |
33 ms |
34048 KB |
sub5_in3.txt |
AC |
171 ms |
34048 KB |
sub5_in4.txt |
AC |
170 ms |
34048 KB |