fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <cstdlib>
  7.  
  8. #define rep( i, l, r ) for (int i = l; i <= r; i++)
  9. #define down( i, l, r ) for (int i = l; i >= r; i--)
  10. #define MS 1009
  11. #define MAX 1073741823
  12.  
  13. using namespace std;
  14.  
  15. int n, m, num[109][9], dp[109][5][20], ans, k;
  16.  
  17. int main()
  18. {
  19. 	scanf("%d%d%d", &n, &m, &k);
  20. 	rep(i, 1, n) rep(j, 1, m) scanf("%d", &num[i][j]);
  21. 	rep(i, 0, 108)  rep(j, 0, 4) rep(a, 0, 19) dp[i][j][a] = -MAX;
  22. 	dp[0][0][0] = 0;
  23. 	rep(i, 0, n-1) rep(j, 0, k)
  24. 	{
  25. 		if (m == 1)
  26. 		{
  27. 			dp[i+1][0][j+0] = max(dp[i+1][0][j+0], dp[i][0][j]);
  28. 			dp[i+1][1][j+1] = max(dp[i+1][1][j+1], dp[i][0][j] + num[i+1][1]);
  29. 			dp[i+1][0][j+0] = max(dp[i+1][0][j+0], dp[i][1][j]);
  30. 			dp[i+1][1][j+0] = max(dp[i+1][1][j+0], dp[i][1][j] + num[i+1][1]);
  31. 		}
  32. 		else
  33. 		{
  34. 			dp[i+1][0][j+0] = max(dp[i+1][0][j+0], dp[i][0][j]);
  35. 			dp[i+1][1][j+1] = max(dp[i+1][1][j+1], dp[i][0][j] + num[i+1][1]);
  36. 			dp[i+1][2][j+1] = max(dp[i+1][2][j+1], dp[i][0][j] + num[i+1][2]);
  37. 			dp[i+1][3][j+2] = max(dp[i+1][3][j+2], dp[i][0][j] + num[i+1][1] + num[i+1][2]);
  38. 			dp[i+1][4][j+1] = max(dp[i+1][4][j+1], dp[i][0][j] + num[i+1][1] + num[i+1][2]);
  39.  
  40. 			dp[i+1][0][j+0] = max(dp[i+1][0][j+0], dp[i][1][j]);
  41. 			dp[i+1][1][j+0] = max(dp[i+1][1][j+0], dp[i][1][j] + num[i+1][1]);
  42. 			dp[i+1][2][j+1] = max(dp[i+1][2][j+1], dp[i][1][j] + num[i+1][2]);
  43. 			dp[i+1][3][j+1] = max(dp[i+1][3][j+1], dp[i][1][j] + num[i+1][1] + num[i+1][2]);
  44. 			dp[i+1][4][j+1] = max(dp[i+1][4][j+1], dp[i][1][j] + num[i+1][1] + num[i+1][2]);
  45.  
  46. 			dp[i+1][0][j+0] = max(dp[i+1][0][j+0], dp[i][2][j]);
  47. 			dp[i+1][1][j+1] = max(dp[i+1][1][j+1], dp[i][2][j] + num[i+1][1]);
  48. 			dp[i+1][2][j+0] = max(dp[i+1][2][j+0], dp[i][2][j] + num[i+1][2]);
  49. 			dp[i+1][3][j+1] = max(dp[i+1][3][j+1], dp[i][2][j] + num[i+1][1] + num[i+1][2]);
  50. 			dp[i+1][4][j+1] = max(dp[i+1][4][j+1], dp[i][2][j] + num[i+1][1] + num[i+1][2]);
  51.  
  52. 			dp[i+1][0][j+0] = max(dp[i+1][0][j+0], dp[i][3][j]);
  53. 			dp[i+1][1][j+0] = max(dp[i+1][1][j+0], dp[i][3][j] + num[i+1][1]);
  54. 			dp[i+1][2][j+0] = max(dp[i+1][2][j+0], dp[i][3][j] + num[i+1][2]);
  55. 			dp[i+1][3][j+0] = max(dp[i+1][3][j+0], dp[i][3][j] + num[i+1][1] + num[i+1][2]);
  56. 			dp[i+1][4][j+1] = max(dp[i+1][4][j+1], dp[i][3][j] + num[i+1][1] + num[i+1][2]);
  57.  
  58. 			dp[i+1][0][j+0] = max(dp[i+1][0][j+0], dp[i][4][j]);
  59. 			dp[i+1][1][j+1] = max(dp[i+1][1][j+1], dp[i][4][j] + num[i+1][1]);
  60. 			dp[i+1][2][j+1] = max(dp[i+1][2][j+1], dp[i][4][j] + num[i+1][2]);
  61. 			dp[i+1][3][j+2] = max(dp[i+1][3][j+2], dp[i][4][j] + num[i+1][1] + num[i+1][2]);
  62. 			dp[i+1][4][j+0] = max(dp[i+1][4][j+0], dp[i][4][j] + num[i+1][1] + num[i+1][2]);
  63. 		}
  64. 	}
  65. 	ans = max(dp[n][0][k], dp[n][1][k]);
  66. 	if (m == 2)
  67. 	{ ans = max(ans, dp[n][2][k]); ans = max(ans, dp[n][3][k]); ans = max(ans, dp[n][4][k]); }
  68. 	printf("%d\n", ans);
  69. 	return 0;
  70. }
Success #stdin #stdout 0s 3344KB
comments (?)
stdin
copy 
3 2 2
1 -3
2 3
-2 3
stdout
copy 
9
https://ideone.com/F3sc0c
BZOJ 1084
language:
C++ (gcc 8.3)
created:
9 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!