fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. //error
  6. #define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
  7.  
  8. void err(istream_iterator<string> it) {}
  9. template<typename T, typename... Args>
  10. void err(istream_iterator<string> it, T a, Args... args) {
  11. 	cerr << *it << " = " << a << endl;
  12. 	err(++it, args...);
  13. }
  14.  
  15. //output
  16. #define output(x) cout << x << endl
  17.  
  18. //input
  19. #define input(x) {int x; cout << x << endl;}
  20.  
  21. //loop
  22. #define f(i, n) for(int i = 0; i < n; i++)
  23.  
  24. #define ll long long
  25.  
  26. typedef struct ABC {
  27. 	vector<ll> v;
  28. 	int idx;
  29.  
  30. 	bool operator<(const ABC& t) const { 
  31.         return (this->idx <= t.idx); 
  32.     } 
  33. }Node;
  34.  
  35. map<Node, int> dp;
  36.  
  37. ll maximum(vector<ll> &input, Node n) {
  38.  
  39. //	cout << "query " << n.idx << " " <<  n.v.size() << endl;
  40.  
  41. 	if (n.idx >= input.size() || n.v.size() == 3) {
  42.  
  43. 		ll sum = 0;
  44. 		f(i, n.v.size()) sum += n.v[i];
  45. 		return sum;
  46. 	}
  47.  
  48. 	if (dp.find(n) != dp.end()) {
  49. 		cout<<n.idx<<" "<<n.v.size()<<endl;
  50. 		return dp[n];
  51. 	}
  52.  
  53. 	bool canHave = true;
  54.  
  55. 	for (int j = 0 ; j < n.v.size() ; j++) {
  56. 		if (input[n.idx] % n.v[j] == 0 || n.v[j] % input[n.idx]  == 0) {
  57. 			canHave = false;
  58. 			break;
  59. 		}
  60. 	}
  61.  
  62. 	ll answer = 0;
  63.  
  64. 	if (canHave) {
  65. 		Node newN;
  66. 		newN.v = n.v;
  67. 		newN.idx = 0;
  68.  
  69. 		newN.v.push_back(input[n.idx]);
  70. 		newN.idx = n.idx + 1;
  71. 		ll a = maximum(input, newN);
  72.  
  73. 		newN.v = n.v;
  74. 		ll b = maximum(input, newN);
  75.  
  76. 		answer = max(a, b);
  77. 	}
  78. 	else {
  79. 		Node newN;
  80. 		newN.v = n.v;
  81. 		newN.idx = n.idx + 1;
  82. 		ll b = maximum(input, newN);
  83.  
  84. 		answer = b;
  85. 	}
  86. 	cout << n.idx << " " <<  n.v.size() << " " <<answer << endl;
  87. 	for(int i = 0; i < n.v.size();i++) {
  88. 		cout<<" : "<<n.v[i]<<endl;
  89. 	}
  90. 	cout<<" --------"<<endl;
  91.  
  92. 	dp[n] = answer;
  93.  
  94. 	return dp[n];
  95. }
  96.  
  97. int main(int argc, char const *argv[]) {
  98. 	ll n = 0;
  99.  
  100. 	cin >> n;
  101.  
  102. 	output(n);
  103.  
  104. 	while (n--) {
  105. 		dp.clear();
  106. 		ll k = 0;
  107. 		cin >> k;
  108. 		ll num = 0;
  109. 		vector<ll> input = {};
  110. 		vector<ll> current = {};
  111.  
  112. 		for(ll i = 0; i < k; i++) {	
  113. 			cin >> num;
  114. 			input.push_back(num);
  115. 		}
  116.  
  117. 		Node n1;
  118. 		n1.idx = 0;
  119.  
  120. //		output("calling function max");
  121. 		maximum(input, n1);
  122.  
  123. 		ll ans = LONG_MIN;
  124.  
  125. 		for (map<Node,int>::iterator it=dp.begin(); it!=dp.end(); ++it) {
  126. 			cout << it->first.idx << " " <<  it->first.v.size()  << " " <<it->second << " ========"<< "\n";
  127.     		if (it->second > ans) {
  128.     			ans = it->second;
  129.     		}
  130. 		}
  131. 		output(ans);
  132. 	}
  133. 	return 0;
  134. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
1
3
3 4 6
stdout
copy 
1
2 2 7
 : 3
 : 4
 --------
2 1 3
 : 3
 --------
1 1 0
 : 3
 --------
2 1 10
 : 4
 --------
2 0 6
 --------
1 0 0
 --------
0 0 0
 --------
2 2 0 ========
2 2 7 ========
7
https://ideone.com/eKbHG1
language:
C++14 (gcc 8.3)
created:
4 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!