fork download 
  1. #include<bits/stdc++.h>
  2. #define ll long long int
  3.  
  4. #define print(a)        for (auto x : a) cout << x << " "; cout << endl
  5. #define print_upto(a,n)        for(int i=0;i<n;i++)    cout<<a[i]<<" "; cout<<endl
  6. #define take(x,n)           for(int i=0;i<n;i++)  cin>>x[i];
  7.  
  8. #define watch(x) cout << (#x) << " is " << (x) << "\n"
  9. #define watch2(x,y) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<"\n"
  10.  
  11. using namespace std;
  12.  
  13. int main() {
  14.  
  15. 	ios_base::sync_with_stdio(false);
  16. 	cin.tie(0);
  17. 	cout.tie(0);
  18.  
  19. #ifndef ONLINE_JUDGE
  20. 	freopen("input.txt", "r", stdin);
  21. 	freopen("output.txt", "w", stdout);
  22. 	freopen("error.txt" , "w" , stderr);
  23. #endif
  24.  
  25. 	ll n;
  26. 	cin >> n;
  27.  
  28. 	ll a[1000003] = {0};
  29. 	for (ll i = 0; i < n; i++) {
  30. 		cin >> a[i];
  31. 	}
  32.  
  33. 	ll dp[1000009] = {0};
  34. 	dp[0] = a[0];
  35. 	dp[1] = a[1];
  36. 	dp[2] = a[2];
  37.  
  38. 	for (ll i = 3; i < n; i++) {
  39. 		ll v = min(dp[i - 2], dp[i - 3]);
  40. 		dp[i] = a[i] + min(dp[i - 1], v);
  41. 	}
  42.  
  43. 	if (n == 1)
  44. 		cout << dp[0] << "\n";
  45. 	else if (n == 2)
  46. 		cout << min(dp[0], dp[1]) << "\n";
  47. 	else {
  48. 		ll v = min(dp[n - 2], dp[n - 3]);
  49. 		cout << min(dp[n - 1], v) << "\n";
  50. 	}
  51.  
  52.  
  53. 	return 0;
  54. }
Success #stdin #stdout 0s 19288KB
comments (?)
stdin 
10
3 2 1 1 2 3 1 3 2 1
stdout 
4
https://ideone.com/XuMQrE
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!