fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <chrono>
  5.  
  6. using namespace std;
  7.  
  8. //O(N)
  9. long long square_sum(const vector<long long>& A){
  10. 	long long ret = 0;
  11. 	int n = A.size();
  12.  
  13. 	long long s0 = 0;	//ΣAi
  14. 	long long s1 = 0;	//ΣΣAi
  15. 	long long s2 = 0;	//Σ(ΣAi)^2
  16. 	for(int i=0; i<n; i++){
  17. 		s0 += A[i];
  18.  
  19. 		ret += (i+1)*s0*s0 - 2*s0*s1 + s2;
  20.  
  21. 		s1 += s0;
  22. 		s2 += s0*s0;
  23. 	}
  24.  
  25. 	return ret;
  26. }
  27.  
  28. //O(N^2)
  29. long long square_sum_O_N2(const vector<long long>& A){
  30. 	long long ret = 0;
  31. 	int n = A.size();
  32.  
  33. 	for(int r=0; r<n; r++){
  34. 		long long s = 0;
  35. 		for(int l=r; l>=0; l--){
  36. 			s += A[l];
  37. 			ret += s*s;
  38. 		}
  39. 	}
  40. 	return ret;
  41. }
  42.  
  43. //O(N^2)
  44. long long square_sum_O_N2_accumulate(const vector<long long>& A){
  45. 	long long ret = 0;
  46. 	int n = A.size();
  47.  
  48. 	vector<long long> acc(n+1, 0);
  49. 	for(int i=0; i<n; i++) acc[i+1] = acc[i] + A[i];
  50. 	for(int l=0; l<n; l++){
  51. 		for(int r=l+1; r<=n; r++){
  52. 			long long s = acc[r]-acc[l];
  53. 			ret += s*s;
  54. 		}
  55. 	}
  56. 	return ret;
  57. }
  58.  
  59. //O(N^3)
  60. long long square_sum_O_N3(const vector<long long>& A){
  61. 	long long ret = 0;
  62. 	int n = A.size();
  63. 	for(int l=0; l<n; l++){
  64. 		for(int r=l; r<n; r++){
  65. 			long long s = 0;
  66. 			for(int i=l; i<=r; i++){
  67. 				s += A[i];
  68. 			}
  69. 			ret += s*s;
  70. 		}
  71. 	}
  72. 	return ret;
  73. }
  74.  
  75. int main(){
  76. 	long long n = 3000;
  77. 	vector<long long> v(n, 1);
  78. 	random_device rnd;
  79. 	mt19937 mt(rnd());
  80. 	uniform_int_distribution<long long> dstr(-10, 10);
  81.  
  82. 	generate(v.begin(), v.end(), [&](){return dstr(mt);});
  83.  
  84. 	long long ans;
  85.  
  86. 	auto s = chrono::system_clock::now();
  87. 	ans = square_sum(v);
  88. 	auto t = chrono::system_clock::now();
  89.  
  90. 	cout << "O(N)   : " << chrono::duration_cast<chrono::milliseconds>(t-s).count() << " ms" << endl;
  91. 	cout << ans << endl;
  92.  
  93. 	s = chrono::system_clock::now();
  94. 	ans = square_sum_O_N2(v);
  95. 	t = chrono::system_clock::now();
  96. 	cout << "O(N^2) : " << chrono::duration_cast<chrono::milliseconds>(t-s).count() << " ms" << endl;
  97. 	cout << ans << endl;
  98.  
  99. 	s = chrono::system_clock::now();
  100. 	ans = square_sum_O_N2_accumulate(v);
  101. 	t = chrono::system_clock::now();
  102. 	cout << "O(N^2) : " << chrono::duration_cast<chrono::milliseconds>(t-s).count() << " ms" << endl;
  103. 	cout << ans << endl;
  104.  
  105.  
  106. 	s = chrono::system_clock::now();
  107. 	ans = square_sum_O_N3(v);
  108. 	t = chrono::system_clock::now();
  109. 	cout << "O(N^3) : " << chrono::duration_cast<chrono::milliseconds>(t-s).count() << " ms" << endl;
  110. 	cout << ans << endl;
  111.  
  112. 	return 0;
  113. }
Success #stdin #stdout 4.19s 3416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
O(N)   : 0 ms
210914757742
O(N^2) : 15 ms
210914757742
O(N^2) : 18 ms
210914757742
O(N^3) : 4159 ms
210914757742
https://ideone.com/2zKyHZ
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!