fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<ll,ll> ii;
  17. typedef vector<int> vi;
  18. typedef long double ld; 
  19. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20. typedef set<int>::iterator sit;
  21. typedef map<int,int>::iterator mit;
  22. typedef vector<int>::iterator vit;
  23.  
  24. int a[2001][2001];
  25. int pos[2001];
  26.  
  27. int main()
  28. {
  29. 	ios_base::sync_with_stdio(0); cin.tie(0);
  30. 	int n, k; cin >> n >> k;
  31. 	for(int i = 0; i < n; i++)
  32. 	{
  33. 		for(int j = 0; j < k; j++)
  34. 		{
  35. 			cin >> a[i][j];
  36. 		}
  37. 	}
  38. 	memset(pos, 0, sizeof(pos));
  39. 	priority_queue<ii, vector<ii>, greater<ii> > pq;
  40. 	for(int i = 0; i < n; i++)
  41. 	{
  42. 		pq.push(mp(0, i));
  43. 	}
  44. 	ll ans = 0;
  45. 	for(int i = 0; i < n*(k+1); i++)
  46. 	{
  47. 		if(pq.empty()) continue;
  48. 		int tmp = pq.top().se; ll score = pq.top().fi;
  49. 		pq.pop();
  50. 		if(pos[tmp] >= k) continue;
  51. 		//cerr<<tmp<<' '<<score<<'\n';
  52. 		score += a[tmp][pos[tmp]];
  53. 		pos[tmp]++;
  54. 		if(pq.empty()) continue;
  55. 		if((score > pq.top().fi)||(score == pq.top().fi && tmp > pq.top().se))
  56. 		{
  57. 			ans++;
  58. 			//cerr<<"FAIL : "<<pq.top().se<<' '<<pq.top().fi<<" vs "<<tmp<<' '<<score<<'\n';
  59. 		}
  60. 		pq.push(mp(score,tmp));
  61. 	}
  62. 	cout<<ans<<'\n';
  63. }
  64.  
Time limit exceeded #stdin #stdout 5s 19120KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NuTy7a
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!