Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <vector>
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include "optimization.h"
- #include <stack>
- #include <string>
- #include <stdlib.h>
- #include <stdio.h>
- #include <vector>
- #include <map>
- #include <unordered_map>
- #include <list>
- #include <set>
- #include <bits/stdc++.h>
- struct vasyna_korobka{
- int ves;
- int tyasheloves;
- };
- bool proverka(vasyna_korobka& a, vasyna_korobka& b){
- return (a.ves + a.tyasheloves < b.ves + b.tyasheloves);
- }
- int main(){
- // freopen("text.in", "r", stdin);
- int n;
- n = readInt();
- std::vector<vasyna_korobka> uborka(n);
- for (int i = 0; i < n; ++i){
- uborka[i].ves = readInt();
- uborka[i].tyasheloves = readInt();
- }
- std::sort(uborka.begin(), uborka.end(), proverka);
- std::priority_queue<int> take;
- int cnt = 1;
- int all = uborka[0].ves;
- int samaya_tyasholaya = uborka[0].ves;
- take.push(all);
- for (int i = 1; i < n; ++i){
- if (all <= uborka[i].tyasheloves){
- cnt++;
- all += uborka[i].ves;
- take.push(uborka[i].ves);
- samaya_tyasholaya = take.top();
- }
- else
- if (samaya_tyasholaya >= uborka[i].ves){
- all = all + uborka[i].ves - samaya_tyasholaya;
- take.pop();
- take.push(uborka[i].ves);
- samaya_tyasholaya = take.top();
- }
- }
- writeInt(cnt);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement