aj30

Untitled

Jul 19th, 2020
766
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.75 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. typedef long long ll;
  3. using namespace std;
  4.  
  5. struct Job
  6. {
  7.     int start, finish, profit;
  8. };
  9.  
  10. bool myfunction(Job s1, Job s2)
  11. {
  12.     return (s1.finish < s2.finish);
  13. }
  14. int binarySearch(Job jobs[], int index)
  15. {
  16.     int lo = 0, hi = index - 1;
  17.  
  18.  
  19.     while (lo <= hi)
  20.     {
  21.         int mid = (lo + hi) / 2;
  22.         if (jobs[mid].finish <= jobs[index].start)
  23.         {
  24.             if (jobs[mid + 1].finish <= jobs[index].start)
  25.                 lo = mid + 1;
  26.             else
  27.                 return mid;
  28.         }
  29.         else
  30.             hi = mid - 1;
  31.     }
  32.  
  33.     return -1;
  34. }
  35. int cnt = 0;
  36. int findMaxProfit(Job arr[], int n)
  37. {
  38.  
  39.     sort(arr, arr + n, myfunction);
  40.  
  41.  
  42.     int *table = new int[n];
  43.     vector<int> tot(n);
  44.     table[0] = arr[0].profit;
  45.     tot[0] = 1;
  46.    
  47.    
  48.     for (int i = 1; i < n; i++)
  49.     {
  50.         int inclProf = arr[i].profit;
  51.         int l = binarySearch(arr, i);
  52.         if (l != -1){
  53.             inclProf += table[l];
  54.             if(inclProf > table[i-1]){
  55.                 table[i] = inclProf;
  56.                 tot[i] = 1+tot[l];
  57.             }
  58.             else{
  59.                 table[i] = table[i-1];
  60.                 tot[i] = tot[i-1];
  61.             }
  62.         }
  63.         else{
  64.             if(inclProf > table[i-1]){
  65.                 table[i] = inclProf;
  66.                 tot[i] = 1;
  67.             }
  68.             else{
  69.                 table[i] = table[i-1];
  70.                 tot[i] = 1;
  71.             }
  72.         }
  73.         // table[i] = max(inclProf, table[i - 1]);
  74.     }
  75.     cnt = tot[n-1];
  76.     int result = table[n - 1];
  77.     // delete[] table;
  78.     // cout<<"tal: "<<endl;
  79.     // for(int i=0;i<n;++i){
  80.     //     cout<<table[i]<<" "<<tot[i]<<endl;
  81.     // }
  82.     return result;
  83. }
  84. int main()
  85. {
  86.     int n ;cin>>n;
  87.     Job arr[n];
  88.    
  89.     long long cost = 0;
  90.     for(int i=0;i<n;++i){
  91.         cin>>arr[i].start>>arr[i].finish>>arr[i].profit;
  92.         cost += arr[i].profit;
  93.     }
  94.     // for(int i=0;i<n;++i){
  95.     //  cout<<arr[i].start<<" "<<arr[i].finish<<" "<<arr[i].profit<<endl;
  96.     //     // cost += arr[i].profit;
  97.     // }
  98.     long long mine = findMaxProfit(arr, n);
  99.  
  100.     cost -= mine;
  101.     // cout<<cnt<<" "<<mine<<endl;
  102.     cout<<n-cnt<<" "<<cost<<endl;
  103. }
  104. /*
  105. 4
  106. 3 10 20
  107. 1 2 50
  108. 6 9 100
  109. 2 100 200
  110.  */
  111.  
  112. // 0805 0830 100
  113. // 0835 0900 100
  114. // 0905 0930 100
  115. // 0935 1000 100
  116. // 1005 1030 100
  117.  
  118. // 0900 1030 100
  119. // 1000 1200 500
  120. // 1100 1200 300
Add Comment
Please, Sign In to add comment