Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <algorithm>
- #include <set>
- #include <ctime>
- #include <cstdlib>
- using namespace std;
- int solve_e_maxx(vector< pair< int ,int> > a, int n)
- {
- sort(a.begin(), a.end());
- vector< int > res;
- set< pair<int , int > > se;
- for(int i = n-1; i >= 0; -- i)
- {
- int t = a[i].first-(i?a[i-1].first:0);
- se.insert( make_pair(a[i].second,i) );
- while(t && !se.empty())
- {
- set< pair<int,int> >::iterator it = se.begin();
- if(it->first <= t)
- {
- t-=it->first;
- res.push_back(it->second);
- }
- else
- {
- se.insert( make_pair(it->first-t, it->second) );
- t = 0;
- }
- se.erase(it);
- }
- }
- return res.size();
- }
- int solve_algo( vector< pair<int, int> > a, int n)
- {
- sort(a.begin(), a.end());
- set< pair<int , int > > se;
- int T = 0;
- for(int i = 0; i < n; ++ i)
- {
- if(T+a[i].second <= a[i].first)
- {
- T+=a[i].second;
- se.insert( make_pair( -a[i].second ,i) );
- }
- else
- if(!se.empty())
- {
- set< pair<int, int> >::iterator it = se.begin();
- if(-(it->first) > (a[i].second))
- {
- T = T+(a[i].second)-(-(it->first));
- se.erase(it);
- se.insert( make_pair(-a[i].second, i));
- }
- }
- }
- return se.size();
- }
- int main()
- {
- srand(time(NULL));
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- int n;
- /* while(1)
- {
- n = rand()%100+1;*/
- cin>>n;
- vector< pair<int, int > > a(n);
- /* for(int i = 0; i < n; ++ i)
- {
- a[i].first = rand()%10000+1;
- a[i].second = rand()%(10000)+1;
- }*/
- for(int i = 0;i < n; ++ i)
- {
- cin>>(a[i].first)>>(a[i].second);//completion, duration
- }
- int re1 = solve_e_maxx(a, n);
- int re2 = solve_algo(a, n);
- // cout<<re1<<" "<<re2<<endl;
- if(re1!=re2)
- {
- cerr<<"Wrong answer\n";
- cout<<n<<endl;
- for(int i = 0; i < n; ++ i)
- {
- cout<<a[i].first<<" "<<a[i].second<<endl;
- }
- // break;
- }
- //}
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment