fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ford(i, n) for(int i = (int)(n) - 1; i >= 0; i--)
  4. #define forn(i, n) for(int i = 0; i < (int)(n); i++)
  5. #define for1(i, n) for(int i = 1; i <= (int)(n); i++)
  6. #define all(x) (x).begin(), (x).end()
  7. #define clr(x) memset(x, 0, sizeof(x))
  8. #define pb push_back
  9. #define mp make_pair
  10. #define prev asdfsdf
  11. #define fi first
  12. #define se second
  13.  
  14. using namespace std;
  15. typedef long double ld;
  16. typedef long long ll;
  17. typedef pair<int, int> PII;
  18. typedef pair<int, int> pii;
  19. typedef vector<int> vi;
  20. typedef long long i64;
  21.  
  22. int nxt() {
  23. 	int x;
  24. 	scanf("%d", &x);
  25. 	return x;
  26. }
  27.  
  28. vector <int> x;
  29.  
  30. vector <vector <int> > ok;
  31.  
  32. void rec(int pos, set <int> used, int sum) {
  33. 	if (sum < -4 || sum > 4) return;
  34. 	if (used.count(0)) {
  35. 		return;
  36. 	}
  37. 	if (sum == 1) {
  38. 		ok.pb(x);
  39. 	}
  40. 	for (int i = -4; i <= 4; ++i) {
  41. 		if (i == 0) continue;
  42. 		set <int> u;
  43. 		u.insert(i);
  44. 		for (int x : used) {
  45. 			u.insert(x + i);
  46. 			u.insert(x);
  47. 		}
  48. 		x.pb(i);
  49. 		rec(pos + 1, u, sum + i);
  50. 		x.pop_back();
  51. 	}
  52. }
  53.  
  54. /*
  55.  *  11
  56. 	-4 -4 3 3 3 
  57. 	-4 -1 3 3 
  58. 	-4 2 3 
  59. 	-3 2 2 
  60. 	-3 4 
  61. 	-2 -1 4 
  62. 	-2 3 
  63. 	-1 -1 -1 4 
  64. 	-1 -1 3 
  65. 	-1 2 
  66. 	1 
  67. */
  68.  
  69. void solve() {
  70. 	rec(0, set <int>(), 0);
  71.  
  72. 	for (auto & t : ok) {
  73. 		sort(all(t));
  74. 	}
  75. 	sort(all(ok));
  76. 	ok.erase(unique(all(ok)), ok.end());
  77.  
  78. 	/*cout << ok.size() << endl;
  79. 	for (auto x : ok) {
  80. 		for (auto y : x) {
  81. 			cout << y << " ";
  82. 		}
  83. 		cout << endl;
  84. 	} */
  85.  
  86. 	int n = nxt();
  87.  
  88. 	vector <long long> v[n];
  89.  
  90. 	set <pair <int, int> > x[10];
  91.  
  92. 	set <pair <int, int> > * y = x + 5;
  93.  
  94. 	int sum = 0;
  95.  
  96. 	long long ans = 0;
  97.  
  98. 	int cur[n];
  99.  
  100. 	auto add = [&](int pos, int x) {
  101. 		ans += v[pos][x];
  102. 		cur[pos] = x;
  103. 		for (int i = 1; i < v[pos].size(); ++i) {
  104. 			if (i == x) continue;
  105. 			y[i - x].insert(mp(v[pos][x] - v[pos][i], pos));
  106. 		}
  107. 	};
  108.  
  109. 	auto erase = [&](int pos, int x) {
  110. 		ans -= v[pos][x];
  111. 		for (int i = 1; i < v[pos].size(); ++i) {
  112. 			if (i == x) continue;
  113. 			y[i - x].erase(mp(v[pos][x] - v[pos][i], pos));
  114. 		}
  115. 	};
  116.  
  117.  
  118.  
  119. 	for (int i = 0; i < n; ++i) {
  120. 		int k = nxt();
  121. 		sum += k;
  122. 		v[i].resize(k + 1);
  123. 		for (int j = 1; j <= k; ++j) {
  124. 			v[i][j] = nxt();
  125. 		}
  126. 	}
  127.  
  128.  
  129.  
  130. 	int used[n];
  131. 	clr(used);
  132.  
  133. 	int phase = 1;
  134.  
  135. 	for (int i = 0; i < n; ++i) {
  136. 		add(i, 1);
  137. 	}
  138. 	cout << ans << " ";
  139. 	for (int i = n + 1; i <= sum; ++i) {
  140. 		long long delta = LLONG_MIN;
  141. 		vector <pair <int, int> > best;
  142. 		for (auto p : ok) {
  143. 			do {
  144. 				++phase;
  145. 				vector <pair <int, int> > cur;
  146. 				cur.reserve(p.size());
  147. 				long long s = 0;
  148. 				for (int d : p) {
  149. 					int ch = -1;
  150. 					for (auto z : y[d]) {
  151. 						if (used[z.se] == phase) continue;
  152. 						ch = z.se;
  153. 						s -= z.fi;
  154. 						used[ch] = phase;
  155. 						break;
  156. 					}
  157. 					if (ch == -1) goto l1;
  158. 					cur.pb(mp(d, ch));
  159. 				}
  160.  
  161. 				if (s > delta) {
  162. 					delta = s;
  163. 					best = cur;
  164. 				}
  165.  
  166. 				l1:;
  167. 			} while(next_permutation(all(p)));
  168. 		}
  169.  
  170. 		for (auto z : best) {
  171. 			erase(z.se, cur[z.se]);
  172. 			add(z.se, cur[z.se] + z.fi);
  173. 		}
  174. 		cout << ans << " ";
  175. 	}
  176. 	cout << "\n";	
  177. }
  178. int main()
  179. {
  180. #ifdef LOCAL
  181. 	freopen("input.txt", "r", stdin);
  182. #endif
  183. 	int t = 1;
  184. 	while (t--) solve();
  185. 	return 0;
  186. }
  187.  
Runtime error #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1dueOv
language:
C++14 (gcc 8.3)
created:
8 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!