fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty