fork download 
  1.  
  2.  
  3. /* * * * * * * * * * * * * * 		
  4. #                          *
  5. #  @Author  AYUSH AGRAWAL  *
  6. #                          *
  7. # * * * * * * * * * * * * */
  8.  
  9.  
  10. #include<bits/stdc++.h>
  11. using namespace std;
  12. #define ll long long int
  13. #define MOD 1000000007
  14. #define M(x) (x%MOD + MOD)%MOD
  15. #define _pb push_back
  16. #define _mp make_pair
  17. #define ff first
  18. #define ss second
  19. #define s(x) scanf("%lld",&x)
  20.  
  21. ll mul(ll x,ll y)
  22. { ll ans=1;
  23.  
  24.   while(y>0)
  25.   { if(y&1)
  26. 	ans=(ans*x)%MOD;
  27. 	y/=2;
  28. 	x=(x*x)%MOD;
  29.   }
  30.  
  31.   return ans;
  32. };
  33.  
  34. /******************************************************************************************************/
  35.  
  36. struct qry
  37. {
  38. 	ll code;
  39. 	ll eat;
  40. 	ll in;
  41. 	bool ans;
  42.  
  43. 	qry()
  44. 	{
  45. 		ans = false;
  46. 	}
  47. };
  48.  
  49. struct slot
  50. {
  51. 	ll code;
  52. 	ll eat;
  53. };
  54.  
  55. bool comp1(struct slot lhs, struct slot rhs)
  56. {
  57. 	return (double)lhs.eat/lhs.code>=(double)rhs.eat/rhs.code;		
  58. }
  59.  
  60. bool comp2(struct qry lhs, struct qry rhs)
  61. {
  62. 	return lhs.eat<rhs.eat;
  63. }
  64.  
  65. bool comp3(struct qry lhs, struct qry rhs)
  66. {
  67. 	return lhs.in<rhs.in;
  68. }
  69.  
  70. int main()
  71. {
  72. 	ll t,g=1;
  73. 	s(t);
  74.  
  75. 	while(t--)
  76. 	{
  77. 		ll d,s,i,cc=0,ee=0;
  78. 		s(d); s(s);
  79.  
  80. 		struct slot st[s];
  81.  
  82. 		for(i=0;i<s;i++)
  83. 			s(st[i].code), s(st[i].eat), cc+=st[i].code;
  84.  
  85. 		sort(st,st+s,comp1);
  86.  
  87. 		struct qry qq[d];
  88.  
  89. 		for(i=0;i<d;i++)
  90. 		{
  91. 			s(qq[i].code);
  92. 			s(qq[i].eat);
  93. 			qq[i].in = i;
  94. 		}
  95.  
  96. 		sort(qq,qq+d,comp2);
  97.  
  98. 		ll qin = 0,diff;
  99. 		double frac,max_code;
  100.  
  101. 		for(i=0;i<s;i++)
  102. 		{
  103. 			frac = (double)st[i].code/st[i].eat;
  104.  
  105. 			while(qin<d && qq[qin].eat<=ee+st[i].eat)
  106. 			{
  107. 				diff = qq[qin].eat-ee;
  108. 				max_code = (double)cc - (double)frac*diff;
  109.  
  110. 				if((double)qq[qin].code<=(double)max_code)
  111. 					qq[qin].ans = true;
  112.  
  113. 				++qin;
  114. 			}
  115.  
  116. 			cc-=st[i].code;
  117. 			ee+=st[i].eat;
  118. 		}
  119.  
  120. 		sort(qq,qq+d,comp3);
  121.  
  122. 		string fin;
  123.  
  124. 		for(i=0;i<d;i++)
  125. 		if(qq[i].ans)
  126. 			fin+='Y';
  127. 		else
  128. 			fin+='N';
  129.  
  130. 		cout<<"Case #"<<g<<": "<<fin<<"\n";
  131. 		++g;
  132. 	}
  133. 	return 0;
  134. }
Success #stdin #stdout 0s 4292KB
comments (?)
stdin 
2
4 2
3 8
6 10
0 18
3 13
10 0
7 3
1 2
4 4
4 4
0 0
stdout 
Case #1: YYNY
Case #2: Y
https://ideone.com/awL83T
language:
C++ (gcc 8.3)
created:
5 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!