fork download 
  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstring>
  4. #include<set>
  5. #include<vector>
  6. #include<map>
  7. #include<algorithm>
  8. #include<sstream>
  9. #include<climits>
  10. #include<utility>
  11. #define MX 100000
  12. #include<queue>
  13. #define fs first
  14. #define sec second
  15. #define vi vector<int>
  16. #define tc(t) int t; scanf("%d",&t); while(t--)
  17. #define pi pair<int, int>
  18. #define TC int T;cin>>T;while(T--)
  19. #define loop(i,a,c) for(int i=0;i<a;i++)
  20. #define loop1(i,a,c) for(int i=1;i<=a;i++)
  21. #define pb(a) push_back(a)
  22. #define all(a) (a).begin(), (a).end()
  23. #define mp(x, y) make_pair((x), (y))
  24. #define ll long long int
  25. #define iter(c) typeof(c.begin())
  26. #define foreach(it, c) for(iter(c) it = c.begin(); it != c.end(); it++)
  27. using namespace std;
  28. map<int,int>m;
  29. int main()
  30. {
  31. 	//test cases
  32. 	tc(t)
  33. 	{
  34. 		int n,d;
  35. 		scanf("%d %d",&n,&d);
  36. 		{
  37. 			ll sum=0;
  38. 			priority_queue<int>v[d];
  39. 			vector<pair<int ,pair<int,int> > >p;
  40. 			pair<int,int>p2;
  41. 			while(n--)
  42. 			{
  43. 				int a,b,c;
  44.  
  45. 				scanf("%d %d %d",&a,&b,&c);
  46. 				//sum is the total number of sadness of teachers initially when nobody has taught anything
  47. 				sum=sum+b*c;
  48. 				p2=mp(a,b);
  49.  
  50. 				//vector p is used to store Si,Di,Ti
  51. 				p.push_back(mp(c,p2));
  52.  
  53.  
  54. 				//we push Si in priority queue from the day the trainer starts teaching till the last day
  55. 				//we will later delete some of them so that lectures are not more than the max lectures
  56. 				for(int i=a-1;i<d;i++)
  57. 				{
  58. 					v[i].push(c);
  59. 				}
  60. 			}
  61. 			ll minus=0;
  62. 			//some indices of the priority queue might have been empty so we fill them with zero
  63. 			for(int i=0;i<d;i++)
  64. 			{
  65. 				v[i].push(0);
  66. 			}
  67. 			//sort vector ac. to Si
  68.  
  69. 			sort(p.rbegin(),p.rend());
  70.  
  71. 			//p contains every teachers Si Di Ti
  72. 			for(int i=0;i<p.size();i++)
  73. 			{
  74. 				//count keeps track of the total lectures taken by a trainer
  75. 				// we wod start deleting the element in the queue when the count of a trainers equals the max value that he can take
  76. 				int count=0;
  77.  
  78. 				//p[i].sec.fs is the first day of teaching of ith teacher
  79. 				//so p[i].sec.fs -1 is the index in priority queue corresponding to the day
  80. 				//we iterate till the last day he could teach which is located at index d-1
  81. 				for(int j=p[i].sec.fs-1;j<d;j++)
  82. 				{
  83. 					if(p[i].fs==v[j].top())
  84. 					{
  85. 						if(count>=p[i].sec.sec)v[j].pop();
  86. 						else
  87. 						{
  88. 							//minus is used to track the number of days for which the 
  89. 							//teacher has been assigned
  90. 							//if minus == d we have solved for the whole days
  91. 							count++;
  92. 							minus++;
  93. 							//decrease the value of front of the queue which is the Si of the trainer
  94. 							// from sum when the trainer has been assigned on a day
  95. 							sum-=v[j].top();
  96. 							//we push intmax to avoid repetition in counting
  97. 							//and to know that the days problem has been solved
  98. 							v[j].push(INT_MAX);
  99. 							if(minus==d)break;
  100. 						}
  101. 					}
  102. 				}
  103. 					if(minus==d)break;
  104. 			}
  105. 				cout<<sum<<endl;	
  106. 		}
  107. 	}
  108. }
  109.  
Time limit exceeded #stdin #stdout 15s 1589248KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/nb2XBS
language:
C++14 (gcc 8.3)
created:
6 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!