fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long int
  5. #define endl '\n'
  6. #define Yes cout << "YES" << endl
  7. #define No cout << "NO" << endl
  8.  
  9. bool cmp (pair <int, int> a, pair <int, int> b) {
  10.     if(a.second == b.second)
  11.         return a.first < b.first;
  12.     return a.second > b.second;
  13. }
  14.  
  15. int main()
  16. {
  17.     ios::sync_with_stdio(false);
  18.     cin.tie(nullptr);
  19.     cout.tie(nullptr);
  20.  
  21.     int T; cin >> T;
  22.     while(T--)
  23.     {
  24.         int N, M; cin >> N >> M;
  25.         vector <int> v(N);
  26.         vector < pair <int, int> > monster(M);
  27.  
  28.         for (int i = 0; i < N; i++) cin >> v[i];
  29.         for (int i = 0; i < M; i++) cin >> monster[i].first; // b[i]
  30.         for (int i = 0; i < M; i++) cin >> monster[i].second; // c[i]
  31.  
  32.         sort (v.begin(), v.end());
  33.         sort (monster.begin(), monster.end()); 
  34.  
  35. 		/*
  36.         Idea -> Finding the largest damaging sword among N swords and avilable c[i] swords
  37.         
  38.         If c[i] > 0, the new sword will be x = max (x, c[i]) so x will not be decreased, 
  39.         so I am updating v[j] if it is greater than c[i]. 
  40.         I am assuming the order of killing monsters will not matter as,
  41.         I am looking for the best sword which can be reused multiple time.
  42.         */
  43.         int i = 0, j = 0;
  44.         while (i < M && j < N) 
  45.         {
  46.             if (v[j] >= monster[i].first) {
  47.                 v[j] = max (v[j],  monster[i].second); // new sword x
  48.                 i++;
  49.             }
  50.             else j++;
  51.         }
  52.  
  53.         sort (v.begin(), v.end());
  54.         sort (monster.begin(), monster.end(), cmp); 
  55.         // sorting c[i] in descending order and if c[i] == c[i+1] than sorting it by b[i] < b[i+1]
  56.  
  57.         // Stage 1 -> counting how many b[i] <= largest sword (v[N-1]) and c[i] != 0
  58.         int ans = 0; i = 0;
  59.         while (i < M && monster[i].second > 0) 
  60.         {
  61.             if(v[N-1] >= monster[i].first)
  62.                 ans++;
  63.             i++;
  64.         }
  65.  
  66.         // Stage 2 -> counting how many swords can be used for eleminating the remaining mosnters where c[i] == 0
  67.         j = 0;
  68.         while (i < M && j < N) 
  69.         {
  70.             if (v[j] >= monster[i].first) {
  71.                 ans++;
  72.                 i++;
  73.             }
  74.             j++;
  75.         }
  76.  
  77.         cout << ans << endl;
  78.     }
  79.  
  80.     return 0;
  81. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Yd3gGX
language:
C++ (gcc 8.3)
created:
6 days 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!