Advertisement
varun1729

Untitled

May 3rd, 2023
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.44 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. class Solution {
  7. public:
  8.     typedef pair<int, int> P; // {last date before expiration, number of apples}
  9.     int eatenApples(vector<int>& apples, vector<int>& days) {
  10.         int ans = 0, n = apples.size();
  11.         // min heap, the pair with the smallest expiration date is on the top
  12.         priority_queue<P, vector<P>, greater<P>> que;
  13.         int i = 0;
  14.         while(i < n || !que.empty()){
  15.             // add today's apples
  16.             if(i < n && apples[i] > 0) que.push({i + days[i] - 1, apples[i]});
  17.             // remove outdate apples
  18.             while(!que.empty() && que.top().first < i) que.pop();
  19.             // get the apple that can be eat today
  20.             if(!que.empty()){
  21.                 auto p = que.top();
  22.                 que.pop();
  23.                 if(p.second > 1) que.push({p.first, p.second - 1});
  24.                 ++ans;
  25.             }
  26.             ++i;
  27.         }
  28.         return ans;
  29.     }
  30. };
  31.  
  32. int main() {
  33.     // Read input from file
  34.     freopen("input.txt", "r", stdin);
  35.     int n;
  36.     cin >> n;
  37.     vector<int> apples(n), days(n);
  38.     for(int i = 0; i < n; ++i) {
  39.         cin >> apples[i];
  40.     }
  41.     for(int i = 0; i < n; ++i) {
  42.         cin >> days[i];
  43.     }
  44.     fclose(stdin);
  45.  
  46.     // Solve problem and print output
  47.     Solution sol;
  48.     int ans = sol.eatenApples(apples, days);
  49.     cout << ans << endl;
  50.  
  51.     return 0;
  52. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement