Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- class Solution {
- public:
- typedef pair<int, int> P; // {last date before expiration, number of apples}
- int eatenApples(vector<int>& apples, vector<int>& days) {
- int ans = 0, n = apples.size();
- // min heap, the pair with the smallest expiration date is on the top
- priority_queue<P, vector<P>, greater<P>> que;
- int i = 0;
- while(i < n || !que.empty()){
- // add today's apples
- if(i < n && apples[i] > 0) que.push({i + days[i] - 1, apples[i]});
- // remove outdate apples
- while(!que.empty() && que.top().first < i) que.pop();
- // get the apple that can be eat today
- if(!que.empty()){
- auto p = que.top();
- que.pop();
- if(p.second > 1) que.push({p.first, p.second - 1});
- ++ans;
- }
- ++i;
- }
- return ans;
- }
- };
- int main() {
- // Read input from file
- freopen("input.txt", "r", stdin);
- int n;
- cin >> n;
- vector<int> apples(n), days(n);
- for(int i = 0; i < n; ++i) {
- cin >> apples[i];
- }
- for(int i = 0; i < n; ++i) {
- cin >> days[i];
- }
- fclose(stdin);
- // Solve problem and print output
- Solution sol;
- int ans = sol.eatenApples(apples, days);
- cout << ans << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement