Niloy007

MaxProfit

Apr 27th, 2021
620
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define Niloy
  3. #define int int64_t
  4. #define MAX 1000
  5. #define MOD 1e9
  6. #define pb push_back
  7. #define pairs pair<int, int>
  8. #define vi vector<int>
  9. #define vb vector<bool>
  10. #define vii vector<pairs>
  11. #define lb lower_bound
  12. #define ub upper_bound
  13. #define endl '\n'
  14. #define llu unsigned long long
  15. using namespace std;
  16. /* ----------------------------------------------------------------------------------- */
  17.  
  18. // Input/Output
  19. #define fastInput ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  20. #define all(x) x.begin(), x.end()
  21. #define square(a) (a * a)
  22. #define mem(a, b) memset(a, b, sizeof(a))
  23.  
  24. // Fractional Number
  25. #define fraction()        cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed, ios::floatfield);
  26.  
  27. #define scan(a)           scanf("%lld", &a);
  28. #define scan2(a, b)       scanf("%lld %lld", &a, &b);
  29. #define scan3(a, b, c)    scanf("%lld %lld %lld", &a, &b, &c);
  30. #define scan4(a, b, c, d) scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
  31.  
  32. #define scanD(a)          scanf("%lf", &a);
  33. #define scanD2(a, b)      scanf("%lf %lf", &a, &b);
  34. #define scanD3(a, b, c)   scanf("%lf %lf %lf", &a, &b, &c);
  35. #define scanD4(a, b, c, d)scanf("%lf %lf %lf %lf", &a, &b, &c, &d);
  36.  
  37.  
  38. #define print(a)           printf("%lld\n", a);
  39. #define print2(a, b)       printf("%lld %lld\n", a, b);
  40. #define print3(a, b, c)    printf("%lld %lld %lld\n", a, b, c);
  41. #define print4(a, b, c, d) printf("%lld %lld %lld %lld\n", a, b, c, d);
  42.  
  43. #define printD(a)          printf("%lf\n", a);
  44. #define printD2(a, b)      printf("%lf %lf\n", a, b);
  45. #define printD3(a, b, c)   printf("%lf %lf %lf\n", a, b, c);
  46. #define printD4(a, b, c, d)printf("%lf %lf %lf %lf\n", a, b, c, d);
  47. #define printTwoD(a)       printf("%.2lf\n", a);
  48.  
  49. // File I/O
  50. #define read(x)  freopen(x, "r", stdin);
  51. #define write(x) freopen(x, "w", stdout);
  52.  
  53. // Loops
  54. #define rep(i, a, n) for (int i = a; i < n; i++)
  55. #define REP(i, a, n) for (int i = a; i <= n; i++)
  56. #define rev(i, n, a) for (int i = n - 1; i >= a; i--)
  57. #define REV(i, n, a) for (int i = n; i >= a; i--)
  58. #define inputArray(a,n) rep(i, 0, n) cin >> a[i];
  59. #define copyArray(a,temp,n) rep(i, 0, n) temp[i]=a[i];
  60. #define printArray(a,n) rep(i, 0, n) cout << a[i] << " "; cout << endl;
  61.  
  62. /* ----------------------------------------------------------------------------------- */
  63.  
  64. #define Cases  cout << "Case " << ++Case << ": ";
  65. #define __test int tt; int Case=0; cin >> tt; while(tt--)
  66. #define showTime cerr << "time = " << (clock() / CLOCKS_PER_SEC) << " sec" << '\n';
  67.  
  68. #define dbgA2(A, n, m) {cout<<"--> "<<#A<<" = \n";rep(i, 0, n){rep(j, 0, m){cout<<A[i][j]<<"";}cout<<"\n";}cout<<"\n";}
  69. #define dbgA(A, n) {cout<<" --> "<<#A<<" = (";rep(i, 0, n)cout<<A[i]<<" ";cout<<")\n";}
  70. #define dbg(args...) {string sss(#args);sss+=',';cout<<" --> ";debugger::call(all(sss), args);cout<<"\n";}
  71.  
  72. /* ----------------------------------------------------------------------------------- */
  73.  
  74. int gcd(int n, int m) { return m ? gcd(m, n % m) : n; }
  75. int lcm(int n, int m) { return n / gcd(n, m) * m; }
  76.  
  77. struct debugger {
  78.     typedef string::iterator si;
  79.     static void call(si it, si ed) {}
  80.     template<typename T, typename ... aT>
  81.     static void call(si it, si ed, T a, aT... rest) {
  82.         string b;
  83.         for(; *it!=','; ++it)
  84.             if(*it!=' ')
  85.                 b+=*it;
  86.         cout << b << "=" << a << " ";
  87.         call(++it, ed, rest...);
  88.     }
  89. };
  90.  
  91. /* ----------------------------------------------------------------------------------- */
  92. void input() {
  93. #ifdef Niloy
  94.     read("input.txt");  
  95.     write("output.txt");
  96. #endif
  97. }
  98.  
  99. /* ----------------------------------------------------------------------------------- */
  100.  
  101.  
  102. class Task {
  103. public:
  104.     int taskId;
  105.     int deadline;
  106.     int profit;
  107.    
  108. };
  109.  
  110. int compare(Task a, Task b) {
  111.         return a.profit > b.profit;
  112. }
  113.  
  114. void solve() {
  115.     Task tasks[] = {{1, 9, 15}, {2, 2, 2}, {3, 5, 18}, {4, 7, 1}, {5, 4, 25}, {6, 2, 20}, {7, 5, 8}, {8, 7, 10}, {9, 4, 12}, {10, 3, 5}};
  116.     int n = 0, size = 10;
  117.     rep(i, 0, size) {
  118.         n = max(n, tasks[i].deadline);
  119.     }
  120.     sort(tasks, tasks + size, compare);
  121.  
  122.     // Print the sorted array based on profit
  123.     rep(i, 0, size) {
  124.         cout << tasks[i].taskId << " " << tasks[i].deadline << " " << tasks[i].profit << endl;
  125.     }
  126.  
  127.     Task a[n];
  128.     memset(a, -1, sizeof(a));
  129.  
  130.     rep(i, 0, size) {
  131.         if (a[tasks[i].deadline - 1].taskId == -1) {
  132.             a[tasks[i].deadline - 1] = tasks[i];
  133.         } else if (a[tasks[i].deadline - 1].taskId != -1) {
  134.             rev(j, tasks[i].deadline - 1, 0) {
  135.                 if (a[j].taskId == -1) {
  136.                     a[j] = tasks[i];
  137.                     break;
  138.                 }
  139.             }
  140.         }
  141.     }
  142.  
  143.     int maxProfit = 0;
  144.     rep(i, 0, n) {
  145.         if (a[i].profit != -1) {
  146.             maxProfit += a[i].profit;
  147.         }
  148.     }
  149.     rep(i, 0, n) {
  150.         cout << "Task ID: " << a[i].taskId << " "
  151.              << " Deadline: " << a[i].deadline << " Profit: " << a[i].profit << endl;
  152.     }
  153.     cout << endl;
  154.     cout << "Max Profit = " << maxProfit << endl;
  155. }
  156.  
  157. int32_t main() {
  158.     // input();
  159.     // fastInput;
  160.     solve();
  161.  
  162.     // __test {
  163.     //  solve();
  164.     // }
  165.  
  166.     // showTime;
  167.     return 0;
  168. }
  169.  
RAW Paste Data