fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. typedef long long ll;
  3. typedef long double ld;
  4. #define FAST_CODE ios_base::sync_with_stdio(false); cin.tie(NULL);
  5. #define pb push_back
  6. using namespace std;
  7. constexpr ll MOD = 1e9+7;
  8. constexpr ll ROW = 70002;
  9. constexpr ll COL = 601;
  10. ll dp[ROW][COL];
  11.  
  12. ll go(ll sum, ll i)
  13. {
  14.  
  15. 	if(sum == 0 && i == 0)
  16. 	{
  17. 		return dp[sum][i] = 1;
  18. 	}
  19.  
  20. 	if(sum < 0 || i < 0)
  21. 	{
  22. 		return 0;
  23. 	}
  24.  
  25. 	if(dp[sum][i]!=-1)
  26. 	{
  27. 		return dp[sum][i];
  28. 	}
  29.  
  30. 	return dp[sum][i] = (go(sum, i-1) + go(sum-i, i-1))%MOD;	
  31.  
  32.  
  33. }
  34.  
  35.  
  36.  
  37. int main() 
  38. {
  39. 	FAST_CODE;
  40. 	for(ll i=0; i<ROW; i++)
  41. 	{
  42. 		for(ll j=0; j<COL; j++)
  43. 		{
  44. 			dp[i][j] = -1;
  45. 		}
  46. 	}
  47.  
  48. 	ll lim;
  49. 	cin>>lim;
  50. 	ll sum = (lim*(lim+1))/2;
  51.  
  52. 	if(sum%2!=0)
  53. 	{
  54. 		cout<<0<<endl;
  55. 		return 0;
  56. 	}
  57. 	// cout<<sum<<lim;
  58. 	cout<<go(sum/2, lim)/2<<endl;
  59. 	return 0;
  60. }
Success #stdin #stdout 0.08s 332112KB
comments (?)
stdin
copy 
7
stdout
copy 
4
https://ideone.com/ZkC32c
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!