fork download 
  1. /*author - Aryan Mittal*/
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #pragma GCC push_options
  6. #pragma GCC optimize ("unroll-loops")
  7.  
  8.  
  9. #define print(a)        for (auto x : a) cout << x << " "; cout << endl
  10. #define print_upto(a,n)        for(int i=0;i<n;i++)    cout<<a[i]<<" "; cout<<endl
  11. #define take(x,n)           for(int i=0;i<n;i++)  cin>>x[i];
  12.  
  13. #define watch(x) cout << (#x) << " is " << (x) << "\n"
  14. #define watch2(x,y) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<"\n"
  15.  
  16. #define ll long long
  17. #define pie_value 3.14159265358979323846
  18.  
  19. int main() {
  20.  
  21. 	// Use ctrl+shift+b ( second option )
  22. 	ios_base::sync_with_stdio(false);
  23. 	cin.tie(0);
  24. 	cout.tie(0);
  25.  
  26. #ifndef ONLINE_JUDGE
  27. 	freopen("input.txt", "r", stdin);
  28. 	freopen("output.txt", "w", stdout);
  29. 	freopen("error.txt" , "w" , stderr);
  30. #endif
  31.  
  32. 	ll n, k;
  33. 	cin >> n >> k;
  34.  
  35. 	ll a[n + 1];
  36. 	for (ll i = 1; i <= n; i++) {
  37. 		cin >> a[i];
  38. 	}
  39.  
  40. 	ll dp_f[n + 3] = {0};
  41. 	ll dp_b[n + 3] = {0};
  42.  
  43. 	if (k == 1) {
  44. 		dp_f[1] = 0;
  45. 		dp_f[2] = a[2];
  46. 		for (ll j = 3 ; j <= n; j++) {
  47. 			dp_f[j] = a[j] + max(dp_f[j - 1], dp_f[j - 2]);
  48. 		}
  49. 	} else if (k == 2) {
  50. 		dp_f[2] = 0;
  51. 		for (ll j = 3 ; j <= n; j++) {
  52. 			dp_f[j] = a[j] + max(dp_f[j - 1], dp_f[j - 2]);
  53. 		}
  54. 	} else {
  55. 		for (ll j = k + 1 ; j <= n; j++) {
  56. 			dp_f[j] = a[j] + max(dp_f[j - 1], dp_f[j - 2]);
  57. 		}
  58. 	}
  59.  
  60. 	dp_b[1] = a[1];
  61. 	dp_b[2] = a[2] + a[1];
  62. 	for (ll i = 3; i <= n; i++) {
  63. 		dp_b[i] = a[i] + max(dp_b[i - 1], dp_b[i - 2]);
  64. 	}
  65.  
  66. 	ll max_ans = INT_MIN;
  67. 	for (ll i = k + 1; i <= n; i++) {
  68. 		max_ans = max(max_ans , dp_b[i] + dp_f[i] - a[i]);
  69. 	}
  70. 	if (k == n) {
  71. 		max_ans = dp_b[n];
  72. 	}
  73.  
  74. 	cout << max_ans << "\n";
  75.  
  76. 	return 0;
  77. }
  78.  
Success #stdin #stdout 0s 4476KB
comments (?)
stdin 
Standard input is empty
stdout 
-2147483648
https://ideone.com/A9Y6ID
language:
C++14 (gcc 8.3)
created:
5 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!