API tools faq
paste
Advertisement
Fastrail08

Air Cownditioning 2 USACO

Fastrail08
May 25th, 2025 (edited)
138
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.97 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Quadruplet{
  4.     public:
  5.     int ai, bi, pi, mi;
  6.    
  7.     Quadruplet(int ai, int bi, int pi, int mi){
  8.         this-> ai = ai;
  9.         this-> bi = bi;
  10.         this-> pi = pi;
  11.         this-> mi = mi;
  12.     }
  13.    
  14.     void display(){
  15.         cout << this-> ai << " " << this-> bi << " " << this-> pi << " " << this-> mi << '\n';
  16.     }
  17. };
  18.  
  19. // Check if the all the stalls are cooled enough
  20. bool ifStallValid(vector<int> &stalls){
  21.     for(int i = 1; i < stalls.size(); i++){
  22.         if(stalls[i] > 0){
  23.             return false;
  24.         }
  25.     }
  26.     return true;
  27. }
  28.  
  29. // Add heat of each cow as per their range
  30. void addCowHeatToStall(int &si, int &ti, int &ci, vector<int> &stalls){
  31.     for(int i = si; i <= ti; i++){
  32.         stalls[i] += ci;
  33.     }
  34. }
  35.  
  36. void GetMinCostToCoolCows(int csf, int &minCost, vector<int> &stalls, unordered_map<int, Quadruplet> &acs,vector<bool> &usedAc){
  37.     //base case
  38.     if(ifStallValid(stalls)){
  39.         minCost = min(minCost, csf);
  40.         return;
  41.     }
  42.    
  43.     // iterate over each ac, to see which should be turned on
  44.     // Mark the ac as used & add the cost, if ac is turned on
  45.     for(auto ac : acs){
  46.         if(!usedAc[ac.first]){
  47.             int acNo = ac.first;
  48.             usedAc[acNo] = true;
  49.             for(int i = ac.second.ai ; i <= ac.second.bi; i++){
  50.                     stalls[i] -= ac.second.pi;
  51.                 }
  52.             GetMinCostToCoolCows(csf + ac.second.mi, minCost, stalls, acs, usedAc);
  53.             for(int i = ac.second.ai; i <= ac.second.bi; i++){
  54.                 stalls[i] += ac.second.pi;
  55.             }
  56.             usedAc[acNo] = false;
  57.         }
  58.     }
  59. }
  60.  
  61. /*
  62. Control of positions - Which AC is to be turned on at which level
  63.  
  64. Consider if the answer was a subset of 4 ACs, and total ACs = 10
  65.  
  66. ----- , ----- , ----- , -----
  67.  
  68. At each level we choose which AC to turn on.
  69.  
  70. AC1,
  71. AC1, AC3
  72. AC1, AC3, AC4
  73. ...
  74.  
  75. OR
  76.  
  77. AC4,
  78. AC4, AC1
  79. AC4, AC1, AC9...
  80.  
  81. We decide which AC would be turned on at which position. At each level we check if the ACs turned on till now cooled down all the stalls or not
  82.  
  83. AC1, AC2, AC3, AC4 ...
  84. AC2, AC1, AC8, AC7 ...
  85. AC5, AC8, AC1, AC10 ...(Answer)
  86.  
  87. At each level, we check if we have found the answer(all required stalls cooled off)
  88.  
  89. */
  90.  
  91. int main() {
  92.     // your code goes here
  93.     int n, m, si, ti, ci, ai, bi, pi, mi;
  94.     cin >> n >> m;
  95.     unordered_map<int, Quadruplet> acs;
  96.     vector<int> stalls (101, 0);
  97.    
  98.     // Add heat of cows to stall
  99.     for(int i = 0; i < n; i++){
  100.         cin >> si >> ti >> ci;
  101.         addCowHeatToStall(si, ti, ci, stalls);
  102.     }
  103.    
  104.     // Create AC array
  105.     for(int i = 0; i < m; i++){
  106.         cin >> ai >> bi >> pi >> mi;
  107.         Quadruplet newAc(ai, bi, pi, mi);
  108.         acs.insert({i, newAc});
  109.     }
  110.    
  111.     // Answer
  112.     int minCost = INT_MAX;
  113.     vector<bool> usedAc(m, false);
  114.     GetMinCostToCoolCows(0, minCost, stalls, acs, usedAc);
  115.     cout << minCost << '\n';
  116. }
  117.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!