Advertisement
Guest User

Untitled

a guest
Dec 16th, 2018
126
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.61 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement