fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define el      	'\n'
  4. #define ft 			first
  5. #define sd 			second
  6. #define mp(x,y)  	make_pair((x),(y))
  7. #define pb(x)    	push_back((x))
  8. #define all(v)  	((v).begin()),((v).end())
  9. #define sz(x)  		((int) (x).size())
  10. #define clr(a,b)	memset(a,b,sizeof(a))
  11. typedef long long ll;
  12. void Yahia74() {
  13. #ifndef ONLINE_JUDGE
  14. 	freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout);
  15. #endif
  16. 	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  17. }
  18. const int N = 1e3 + 74, OO = 0x3f3f3f3f, MOD = (int) 1e9 + 7;
  19.  
  20. vector<pair<int, int> > adj[N];
  21. int main() {
  22. 	Yahia74();
  23. 	int T;
  24. 	cin >> T;
  25. 	while (T--) {
  26. 		int com, budget;
  27. 		int numOfComp = 1;
  28. 		map<string, int> mp;
  29. 		cin >> com >> budget;
  30. 		for (int i = 0; i <= 1004; ++i)
  31. 			adj[i].clear();
  32. 		for (int i = 0; i < com; ++i) {
  33. 			string s, t;
  34. 			int quality, price;
  35. 			cin >> s >> t >> price >> quality;
  36. 			if (mp.find(s) == mp.end())
  37. 				mp[s] = numOfComp++;
  38. 			adj[mp[s]].pb(mp(price,quality));
  39. 		}
  40. 		for (int i = 1; i < numOfComp; i++) {
  41. 			sort(all(adj[i])); // sorting in price order then quality
  42. 			for (int j = 1; j < sz(adj[i]); j++) {
  43. 				while (adj[i][j].sd <= adj[i][j - 1].sd && j < sz(adj[i]))
  44. 					adj[i].erase(adj[i].begin() + j); // erase all unsafely components that have higher price with lower quality
  45. 			}
  46. 		}
  47. 		set<int> totQ ;
  48. 		for (int i = 1; i < numOfComp; i++)
  49. 			for (int j = 0; j < sz(adj[i]); j++)
  50. 				totQ.insert(adj[i][j].sd);
  51. 		int idx[1005]={}; // pointer in each components refer to current quality so far.
  52. 		int ans = -1;
  53. 		bool flag = false;
  54. 		for (auto i : totQ) {
  55. 			ll tot = 0;
  56. 			for (int j = 1; j < numOfComp; j++) {
  57. 				while (adj[j][idx[j]].sd < i && idx[j] < sz(adj[j]))
  58. 					idx[j]++;
  59. 				if (idx[j] == sz(adj[j])) { // break if I reach the end of any components because that is the maximum I will get
  60. 					flag = true;
  61. 					break;
  62. 				}
  63. 				tot += (ll) adj[j][idx[j]].ft;
  64. 			}
  65. 			if (tot > budget || flag)
  66. 				break;
  67. 			ans = i;
  68. 		}
  69. 		cout << ans << el;
  70. 	}
  71. 	return 0;
  72. }
  73. /*
  74.  
  75.  
  76.  
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  */
  98.  
Success #stdin #stdout 0s 15272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GNcE2r
language:
C++14 (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!