Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- typedef long long ll;
- using namespace std;
- struct Job
- {
- int start, finish, profit;
- };
- bool myfunction(Job s1, Job s2)
- {
- return (s1.finish < s2.finish);
- }
- int binarySearch(Job jobs[], int index)
- {
- int lo = 0, hi = index - 1;
- while (lo <= hi)
- {
- int mid = (lo + hi) / 2;
- if (jobs[mid].finish <= jobs[index].start)
- {
- if (jobs[mid + 1].finish <= jobs[index].start)
- lo = mid + 1;
- else
- return mid;
- }
- else
- hi = mid - 1;
- }
- return -1;
- }
- int cnt = 0;
- int findMaxProfit(Job arr[], int n)
- {
- sort(arr, arr + n, myfunction);
- int *table = new int[n];
- vector<int> tot(n);
- table[0] = arr[0].profit;
- tot[0] = 1;
- for (int i = 1; i < n; i++)
- {
- int inclProf = arr[i].profit;
- int l = binarySearch(arr, i);
- if (l != -1){
- inclProf += table[l];
- if(inclProf > table[i-1]){
- table[i] = inclProf;
- tot[i] = 1+tot[l];
- }
- else{
- table[i] = table[i-1];
- tot[i] = tot[i-1];
- }
- }
- else{
- if(inclProf > table[i-1]){
- table[i] = inclProf;
- tot[i] = 1;
- }
- else{
- table[i] = table[i-1];
- tot[i] = 1;
- }
- }
- // table[i] = max(inclProf, table[i - 1]);
- }
- cnt = tot[n-1];
- int result = table[n - 1];
- // delete[] table;
- // cout<<"tal: "<<endl;
- // for(int i=0;i<n;++i){
- // cout<<table[i]<<" "<<tot[i]<<endl;
- // }
- return result;
- }
- int main()
- {
- int n ;cin>>n;
- Job arr[n];
- long long cost = 0;
- for(int i=0;i<n;++i){
- cin>>arr[i].start>>arr[i].finish>>arr[i].profit;
- cost += arr[i].profit;
- }
- // for(int i=0;i<n;++i){
- // cout<<arr[i].start<<" "<<arr[i].finish<<" "<<arr[i].profit<<endl;
- // // cost += arr[i].profit;
- // }
- long long mine = findMaxProfit(arr, n);
- cost -= mine;
- // cout<<cnt<<" "<<mine<<endl;
- cout<<n-cnt<<" "<<cost<<endl;
- }
- /*
- 4
- 3 10 20
- 1 2 50
- 6 9 100
- 2 100 200
- */
- // 0805 0830 100
- // 0835 0900 100
- // 0905 0930 100
- // 0935 1000 100
- // 1005 1030 100
- // 0900 1030 100
- // 1000 1200 500
- // 1100 1200 300
Add Comment
Please, Sign In to add comment