fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <queue>
  5. #define ll long long
  6. using namespace std;
  7. const int MX = 1010;
  8. typedef pair<ll, ll> ii;
  9.  
  10. int main() {
  11. 	ll n, k; cin >> n >> k;
  12. 	ll s[MX][MX];
  13. 	ll cur[MX]; 
  14. 	for (ll i = 0; i < n; i++) {
  15. 		cur[i] = 0;
  16. 	}
  17. 	for (ll i = 0; i < n; i++) {
  18. 		for (ll j = 0; j < k; j++) {
  19. 			ll a; cin >> a;
  20. 			if (j) {
  21. 				s[i][j] = s[i][j-1]+a;
  22. 			}
  23. 			else {
  24. 				s[i][j] = a;
  25. 			}
  26. 		}
  27. 	}
  28. 	priority_queue<ii, vector<ii>, greater<ii> > pq;
  29. 	for (ll i = 0; i < n; i++) { 
  30. 		pq.push(ii(0, i));
  31. 	}
  32. 	ll ans = 0;
  33. 	while (!pq.empty()) {
  34. 		ii u = pq.top();
  35. 		pq.pop();
  36. 		ll sc = u.first, id = u.second;
  37. 		if (cur[id] < k) {
  38. 			sc = s[id][cur[id]++];
  39. 			pq.push(ii(sc, id));
  40. 			ii v = pq.top();
  41. 			if (v.second != id) {
  42. 				ans++;
  43. 			}
  44. 		}
  45. 	}
  46. 	cout << ans << '\n';
  47. 	return 0;
  48. }
Success #stdin #stdout 0s 11336KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/tCsNi8
language:
C++14 (gcc 8.3)
created:
7 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!