Th3NiKo

stack po

Apr 29th, 2018
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.77 KB | None | 0 0
  1. #include <iostream>
  2. #include <stack>
  3.  
  4. using namespace std;
  5.  
  6. struct Bucket{
  7. public:
  8.     int height;
  9.     int radius;
  10.     int ground;
  11. };
  12.  
  13. int main()
  14. {
  15.     int ile;
  16.     cin >> ile;
  17.     for(int c = 0; c < ile; c++){
  18.     stack<Bucket> tower;
  19.     int hightestPoint = 0;
  20.     int bucketCount;
  21.     cin >> bucketCount;
  22.     Bucket temp;
  23.     Bucket temporary; //Used to speed up a bit
  24.     int maksimum;
  25.     int sum;
  26.     int counter = 0; //Its size of the Stack. Used it because thought its faster then empty() function
  27.     for(int i = 0; i < bucketCount; i++){
  28.         cin >> temp.radius >> temp.height;
  29.         maksimum = -1;
  30.         sum = 0;
  31.         if(counter == 0){
  32.             temp.ground = 0;
  33.             tower.push(temp);
  34.             counter++;
  35.         } else {
  36.             if(temp.radius < tower.top().radius){ //If bucket is narrower then push it
  37.                 temp.ground = tower.top().ground;
  38.                 tower.push(temp);
  39.                 counter++;
  40.             } else { //If bucket is wider
  41.                 while((counter > 0) && temp.radius >= (temporary = tower.top()).radius){ //Pop and search for new ground (maximum)
  42.                     sum = temporary.height + temporary.ground;
  43.                     if(maksimum < sum){
  44.                         maksimum = sum;
  45.                     }
  46.                     tower.pop();
  47.                     counter--;
  48.                 }
  49.                 temp.ground = maksimum; //Set ground for new bucket
  50.                 tower.push(temp);
  51.                 counter++;
  52.             }
  53.         }
  54.         sum = temp.height + temp.ground; //Meantime find highest point in stack
  55.         if(hightestPoint < sum){
  56.             hightestPoint = sum;
  57.         }
  58.     }
  59.     cout << hightestPoint << endl;
  60.     }
  61.  
  62.  
  63.     return 0;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment