SHARE
TWEET

Untitled

a guest Dec 16th, 2018 103 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. struct Task {
  9.     int d;
  10.     long long w;
  11.     bool isDelayed = false;
  12.     bool operator<(const Task &r) const {
  13.         if (isDelayed) return w > r.w;
  14.         if (d != r.d) return d > r.d;
  15.         return w > r.w;
  16.     }
  17. };
  18.  
  19. int main() {
  20.     freopen("schedule.in", "r", stdin);
  21.     freopen("schedule.out", "w", stdout);
  22.     int n;
  23.     cin >> n;
  24.     vector <Task> tasks(n);
  25.     set <int, std::greater<int> > deadlineSet;
  26.     deadlineSet.insert(0);
  27.     for (int i = 0; i < n; i++) {
  28.         cin >> tasks[i].d >> tasks[i].w;
  29.         deadlineSet.insert(tasks[i].d);
  30.     }
  31.     sort(tasks.begin(), tasks.end());
  32.     vector <int> deadline;
  33.     for (int d : deadlineSet)
  34.         deadline.push_back(d);
  35.  
  36.     int it1 = 0, it2 = 0;
  37.  
  38.     set <Task> delayedTasks;
  39.  
  40.     for (int i = 0; i < deadline.size() - 1; i++) {
  41.         int curD = deadline[i];
  42.         int prevD = deadline[i + 1];
  43.         while (it2 < n && tasks[it2].d == curD) it2++;
  44.  
  45.         for (int j = it1; j < it2; j++) {
  46.             tasks[j].isDelayed = true;
  47.             delayedTasks.insert(tasks[j]);
  48.         }
  49.         for (int j = curD; j != prevD && !delayedTasks.empty(); j--)
  50.             delayedTasks.erase(delayedTasks.begin());
  51.         it1 = it2;
  52.     }
  53.     for (int i = 0; i < tasks.size(); i++) {
  54.         if (tasks[i].d == 0) {
  55.             tasks[i].isDelayed = true;
  56.             delayedTasks.insert(tasks[i]);
  57.         }
  58.     }
  59.  
  60.  
  61.     long long penalty = 0;
  62.     for (Task t : delayedTasks)
  63.         penalty += t.w;
  64.     cout << penalty;
  65. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top