fork download 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. using namespace std;
  6. #define re(i, n) for (int i=0; i<n; i++)
  7. #define re1(i, n) for (int i=1; i<=n; i++)
  8. #define re2(i, l, r) for (int i=l; i<r; i++)
  9. #define re3(i, l, r) for (int i=l; i<=r; i++)
  10. #define rre(i, n) for (int i=n-1; i>=0; i--)
  11. #define rre1(i, n) for (int i=n; i>0; i--)
  12. #define rre2(i, r, l) for (int i=r-1; i>=l; i--)
  13. #define rre3(i, r, l) for (int i=r; i>=l; i--)
  14. const int MAXN = 3610, INF = ~0U >> 2;
  15. int n, m, A[MAXN], F[2][MAXN][3], res = 0;
  16. void init()
  17. {
  18. 	scanf("%d%d", &n, &m);
  19. 	re(i, n) scanf("%d", &A[i]);
  20. }
  21. void solve()
  22. {
  23. 	if (!n) return; else if (n == m) {
  24. 		res = 0; re(i, n) res += A[i];
  25. 		int minv = INF; re(i, n) if (A[i] < minv) minv = A[i]; res -= minv; return;
  26. 	}
  27. 	re3(i, 0, m) re(j, 3) re(k, 2) F[k][i][j] = -INF; F[0][0][0] = F[0][1][1] = 0; bool FF = 0; int _j;
  28. 	re2(i, 1, n) {
  29. 		F[!FF][0][0] = 0; F[!FF][0][1] = F[!FF][0][2] = -INF;
  30. 		if (i + 1 <= m) _j = i + 1; else _j = m;
  31. 		re1(j, _j) {
  32. 			F[!FF][j][0] = F[FF][j][0] >= F[FF][j][2] ? F[FF][j][0] : F[FF][j][2];
  33. 			F[!FF][j][1] = F[FF][j - 1][0];
  34. 			F[!FF][j][2] = (F[FF][j - 1][1] >= F[FF][j - 1][2] ? F[FF][j - 1][1] : F[FF][j - 1][2]) + A[i];
  35. 		}
  36. 		FF = !FF;
  37. 	}
  38. 	re(i, 3) if (F[FF][m][i] > res) res = F[FF][m][i];
  39. 	if (n == 1) return;
  40. 	re3(i, 0, m) re(j, 3) re(k, 2) F[k][i][j] = -INF; F[0][1][2] = A[0]; FF = 0;
  41. 	re2(i, 1, n) {
  42. 		F[!FF][0][0] = 0; F[!FF][0][1] = F[!FF][0][2] = -INF;
  43. 		if (i + 1 <= m) _j = i + 1; else _j = m;
  44. 		re1(j, _j) {
  45. 			F[!FF][j][0] = F[FF][j][0] >= F[FF][j][2] ? F[FF][j][0] : F[FF][j][2];
  46. 			F[!FF][j][1] = F[FF][j - 1][0];
  47. 			F[!FF][j][2] = (F[FF][j - 1][1] >= F[FF][j - 1][2] ? F[FF][j - 1][1] : F[FF][j - 1][2]) + A[i];
  48. 		}
  49. 		FF = !FF;
  50. 	}
  51. 	re2(i, 1, 3) if (F[FF][m][i] > res) res = F[FF][m][i];
  52. }
  53. void pri()
  54. {
  55. 	printf("%d\n", res);
  56. }
  57. int main()
  58. {
  59.     init();
  60.     solve();
  61.     pri();
  62.     return 0;
  63. }
  64.  
Success #stdin #stdout 0.01s 2780KB
comments (?)
stdin 
5 3
2
0
3
1
4
stdout 
6
https://ideone.com/PBIKCs
language:
C++ (gcc 8.3)
created:
12 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!