Untitled
unknown
plain_text
24 days ago
1.4 kB
3
Indexable
#include <bits/stdc++.h> using namespace std ; #define For(n) for(long long i = 0; i < n; i++) #define endl '\n' #define int long long #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //***********************Nah I would win*************************/ void Gojo(){ int n , sh = 0 ;cin>>n; vector<int> v= {0}; map<int,int> mp; for(int i = 1; i <= n ; i++){ int x , y;cin>>x >> y; if(!mp[x]) v.push_back(x); mp[x] += y; } sort(v.begin() , v.end()); int shots = 0; priority_queue<int,vector<int>> pq; for(int i = 1; i < v.size() ; i++){ sh += v[i] - v[i-1]; // cout << sh <<' '<< shots<< endl; if(pq.empty()){ if(sh >= mp[v[i]]){ sh -= mp[v[i]]; pq.push(mp[v[i]]); } else shots++; continue; } if(sh >= mp[v[i]]){ sh -= mp[v[i]]; pq.push(mp[v[i]]); } else{ shots++; if(mp[v[i]] < pq.top()){ sh += pq.top() - mp[v[i]]; pq.pop(); } } } cout << shots; } signed main() { fast int Tt =1; // cin>>Tt; while (Tt--){ Gojo(); cout << endl; } }
Editor is loading...
Leave a Comment