fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. namespace bijiEnak {
  3. 	using namespace std;
  4. 	using ll = long long;
  5. 	#define int long long // on or off
  6. 	#define vi vector<int>
  7. 	#define vi2D vector<vi>
  8. 	#define pii pair<int, int>
  9. 	#define fr first
  10. 	#define sc second
  11. 	#define mpr make_pair
  12. 	#define umap unordered_map
  13. 	#define biji ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);    
  14. 	//lower_bound(x) : >= x
  15. 	//upper_bound(x) : > x
  16. 	const int MOD = 1e9 + 7;
  17. 	const int MAXN = 2e5 + 1;
  18. 	const string input = {'_', 'i', 'n', 'p', 'u', 't', '.', 't', 'x', 't'};
  19. 	const string output = {'_', 'o', 'u', 't', 'p', 'u', 't', '.', 't', 'x', 't'};
  20. 	const string input_r = {'r'};
  21. 	const string output_w = {'w'};
  22. }
  23. using namespace bijiEnak;
  24.  
  25. void tcsolve() {
  26. 	int N, K; cin >> N >> K;
  27.  
  28. 	vector<vector<pii>> A(K);
  29. 	for(int i = 0; i < N; i++) {
  30. 		for(int j = 0; j < K; j++) {
  31. 			int t1; cin >> t1;
  32. 			A[j].push_back({t1, i});
  33. 		}
  34. 	}
  35. 	vector<vi> u(N, vi(K+1));
  36. 	for(int i = 0; i < N; i++) {
  37. 		for(int j = 0; j < K; j++) {
  38. 			cin >> u[i][j];
  39. 		}
  40. 	}
  41. 	for(int i = 0; i < K; i++) {
  42. 		sort(A[i].begin(), A[i].end());
  43. 	}
  44.  
  45. 	vector<int> list(N), gt(K), id(K, -1);
  46. 	int ans = 0;
  47. 	bool sw = true;
  48. 	while(sw) {
  49. 		set<int> upd;
  50. 		for(int i = 0; i < K; i++) {
  51. 			while(id[i]+1 < N && A[i][id[i]+1].fr <= gt[i]) {
  52. 				id[i]++;
  53. 				list[id[i]]++;
  54. 				if(list[id[i]] >= K) upd.insert(id[i]);
  55. 			}
  56. 		}
  57.  
  58. 		sw = false;
  59. 		for(auto i : upd) {
  60. 			ans++;
  61. 			sw = true;
  62. 			for(int j = 0; j < K; j++) {
  63. 				gt[j] += u[j][i];
  64. 			}
  65. 		}
  66. 	}
  67. 	cout << ans;
  68. }
  69.  
  70. signed main() {
  71. 	freopen(input.c_str(), input_r.c_str(), stdin);
  72. 	freopen(output.c_str(), output_w.c_str(), stdout);
  73.  
  74. 	biji int t = 1;
  75. 	// cin >> t;
  76. 	while(t--) tcsolve();
  77.  
  78. 	return 0;
  79. }
  80. /*                                                           DOGE
  81. 							  ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣤⠤⠤⠴⠒⠒⠒⠶⠶⠶⠤⠤⠴⠶⠶⠤⠤⠤⠤⠤⠤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  82. 							  ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⠟⠉⢀⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⢀  ⣈⠱⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  83. 							  ⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⠟⢁⣠⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀  ⠙⣷⡈⠛⢦⣄⠀⠀⠀⠀⠀⠀⠀⠀
  84. 							  ⠀⠀⠀⠀⠀⠀⠀⢀⡴⠻⠋⣺⣽⡿⠀⠀⠀⠀⣀⡀⠀⠀⠆⠀⠀⠀⠀⠀⠀⢠⣴⣦⣀⠀⠀⠀ ⠘⣿⣦⡀⠙⢷⣄⠀⠀⠀⠀⠀⠀
  85. 							  ⠀⠀⠀⠀⠀⣀⣴⠟⠁⡠⣴⡇⡸⠁⠀⢠⣾⣿⣿⣿⣷⣠⠀⠀⠀⠀⠀⠀⠀⢼⣿⣿⣿⣿⣦⠀ ⠀⢸⠹⣷⣄⠀⠙⣿⡀⠀⠀⠀⠀
  86. 							  ⠀⠀⢰⡞⠉⠁⠀⠤⠊⢠⡿⢱⠇⠀⠐⢛⡿⠿⠿⢿⡟⠁⠀⠀⠀⠀⠀⠀⠀⠈⢿⠛⣿⣿⠛⠁⠀⠹⡷⣿⡇⠳⢄⡈⠳⢶⣦⡀⠀
  87. 							  ⠀⠠⣾⠃⠀⡀⠀⠀⠀⢸⡇⣿⠀⠀⠀⠀⠀⠀⣠⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢢⠀⠀⠀⠀⠀⠀⠹⣿⡇⠀⢄⢈⠢⣀⣿⡷⠦
  88. 							  ⠀⣼⡷⠀⢀⠔⠂⡰⠁⢈⡇⡇⠀⠀⠀⠀⢀⡴⠁⠀⠀⣠⣶⣶⣿⣿⣿⣶⣦⡀⠀⠀⠳⡀⠀⠀⠀⠀⠀⣿⣧⡀⠀⡙⠱⣌⢻⣿⡂
  89. 							  ⠰⢿⣧⠞⢁⡤⠊⠀⠀⣼⣇⡇⠀⡠⠔⠊⠁⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀⠀⠀⠈⠑⠢⢄⠀⢠⣿⡟⡇⠠⡘⢦⠈⢺⣯⠁
  90. 							  ⠀⠸⣿⠶⠋⣠⠎⢀⡞⠙⣿⡇⠀⡇⣸⡀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀⠀⣀⠈⡆⣸⣿⡻⠀⠀⠻⣄⡳⣼⣿⡀
  91. 							  ⠀⠀⢿⣶⠏⢁⣶⠟⠀⠀⣿⣧⠀⠀⣿⣿⡄⠀⠀⠀⠀⠀⠈⠉⢻⣿⣛⠉⠀⠀⠀⠀⠀⢠⣾⣿⡆⠁⣿⡟⡇⠀⣦⡑⠂⣱⣿⣿⠇
  92. 							  ⠀⠀⠈⢻⣷⡊⠀⢀⣀⢤⢿⡟⢴⠄⠘⣻⣿⣄⡀⠀⠀⠀⣀⣠⢿⡿⣄⣀⡀⠀⠀⠠⣴⢿⣿⡿⠁⢰⣿⡇⢣⠀⢌⣣⣷⠟⠁⠀⠀
  93. 							  ⠀⠀⠀⠀⠙⣿⣿⣋⡿⢫⣿⣧⣰⠀⠀⢇⢻⣏⠉⡛⡟⠋⠉⠀⢸⡇⠀⠉⠉⣻⣿⠟⠁⢰⡟⠀⠀⣼⣿⣇⢠⡇⣸⠟⠏⠀⠀⠀⠀
  94. 							  ⠀⠀⠀⠀⠀⠘⠿⠿⠶⣿⢿⣿⡏⡄⠀⠈⣶⢿⡀⢸⣷⠀⠀⠀⠸⠀⠀⠀⢀⣿⡟⠀⢠⡿⠀⠀⣄⠹⠻⣿⣄⣹⠏⠀⠀⠀⠀⠀⠀
  95. 							  ⠀⠀⠀⠀⠀⠀⠀⣰⢸⡏⠀⢼⡟⢡⡀⠀⠸⣈⢷⡈⢻⡄⠀⠀⠀⠀⠀⠀⢸⡟⠁⢠⣿⠃⢸⣾⣿⠀⠀⢻⡙⠏⠀⠀⠀⠀⠀⠀⠀
  96. 							  ⠀⠀⠀⠀⠀⠀⠀⢉⢸⠁⠀⠘⢇⣾⠁⠀⠀⠙⡆⠳⡌⢷⡀⠀⠀⠀⠀⣠⡟⣠⣶⡿⠃⠈⡈⠛⣇⠀⠀⢸⠧⠀⠀⠀⠀⠀⠀⠀⠀
  97. 							  ⠀⠀⠀⠀⠀⠀⠀⢸⣸⡆⠀⠀⢸⣡⣶⣇⠀⠀⠈⢦⡙⢦⡛⠶⠦⠤⠖⣫⣾⣿⡿⠀⣤⢠⣇⠀⠁⠀⢠⢿⡀⠀⠀⠀⠀⠀⠀⠀⠀
  98. 							  ⠀⠀⠀⠀⠀⠀⠀⠀⣏⢿⡄⠀⠘⢻⣿⠿⡇⠀⠀⠀⠉⠪⣿⣿⣶⣶⣾⣟⡩⠀⠀⠀⣿⣼⡟⠀⠀⠀⡞⣤⠇⠀⠀⠀⠀⠀⠀⠀⠀
  99. 							  ⠀⠀⠀⠀⠀⠀⠀⠀⠘⡌⣷⡀⠀⠈⢻⣴⣷⣶⠀⠀⠀⡀⠀⠉⠚⠓⠚⠁⠀⠀⠀⠐⣿⠿⠀⠀⠀⡸⢁⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀
  100. 							  ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣎⠃⠀⠀⠀⠋⢃⣸⡺⠂⠀⣧⡼⢷⡄⢠⣄⡄⢀⣼⡟⣰⠻⠀⠀⠀⡰⢡⣿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀
  101. 							  ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠣⡀⠀⠀⠀⠛⠙⠁⠀⠘⠛⠁⢻⣿⠋⣿⡧⠈⢈⡴⠁⠀⠀⠀⠀⢁⠜⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  102. 							  ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⡞⠉⠀⠙⠁⠰⠋⠀⠀⠀⠀⠀⠴⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  103. 							  ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  104. 							  ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  105. 							  ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠐⠀⠒⠲⠀⠀⡀⠰⠐⠁⠐⡀⠃⠀⠀
  106. */
Success #stdin #stdout 0.01s 5544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/saC2Np
language:
C++ (gcc 8.3)
created:
325 days 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!