fork(1) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. int H, W, a[203][203], lt[403], rt[403], dp[403][203][203];
  5. int main() {
  6. 	cin >> H >> W;
  7. 	for (int i = 0; i < H; i++) {
  8. 		for (int j = 0; j < W; j++) cin >> a[i][j];
  9. 	}
  10. 	for (int i = 0; i < H; i++) lt[i] = 0;
  11. 	for (int i = 0; i < W; i++) rt[i] = i + 1;
  12. 	for (int i = H; i < H + W - 1; i++) lt[i] = i - H + 1;
  13. 	for (int i = W; i < H + W - 1; i++) rt[i] = W;
  14. 	dp[0][0][0] = a[0][0];
  15. 	for (int i = 1; i < H + W - 1; i++) {
  16. 		for (int j = lt[i]; j < rt[i]; j++) {
  17. 			for (int k = lt[i]; k < rt[i]; k++) {
  18. 				int p = (j != k ? a[i - j][j] + a[i - k][k] : a[i - j][j]);
  19. 				for (int dj = -1; dj <= 0; dj++) {
  20. 					for (int dk = -1; dk <= 0; dk++) {
  21. 						if (j + dj >= 0 && k + dk >= 0) dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j + dj][k + dk] + p);
  22. 					}
  23. 				}
  24. 			}
  25. 		}
  26. 	}
  27. 	cout << dp[H + W - 2][W - 1][W - 1] << endl;
  28. 	return 0;
  29. }
Success #stdin #stdout 0s 68480KB
comments (?)
stdin
copy 
2 6
8 6 9 1 2 0
1 0 0 1 1 1
stdout
copy 
30
https://ideone.com/bixNmF
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!