Th3NiKo

Wieża z wiader

Apr 16th, 2018
161
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.60 KB | None | 0 0
  1. #include <iostream>
  2. #include <stack>
  3.  
  4. using namespace std;
  5.  
  6. class Bucket{
  7. public:
  8.     int height;
  9.     int radius;
  10.     int ground;
  11. };
  12.  
  13.  
  14. int main()
  15. {
  16.  
  17.     int ile;
  18.     cin >> ile;
  19.     for(int p = 0; p < ile; p++){
  20.         stack<Bucket> stos;
  21.         int hightestPoint = 0;
  22.         int bucketCount;
  23.         cin >> bucketCount;
  24.         for(int i = 0; i < bucketCount; i++){
  25.             Bucket temp;
  26.             cin >> temp.radius >> temp.height;
  27.             if(stos.empty()){
  28.                 temp.ground = 0;
  29.                 stos.push(temp);
  30.             } else {
  31.                 if(temp.radius < stos.top().radius){ //Jezeli wiadro jest wezsze to
  32.                     temp.ground = stos.top().ground;
  33.                     stos.push(temp);
  34.                 } else { //Szersze (szukamy maksimum z wezszych wiader)
  35.                     int maksimum = -1;
  36.                     while(!stos.empty() && temp.radius >= stos.top().radius){ //Dopoki wiadro ktore trzymamy jest szersze od tych ze stosu
  37.                         if(maksimum < stos.top().height + stos.top().ground){
  38.                             maksimum = stos.top().height + stos.top().ground; //znalezlismy nowego maksa
  39.                         }
  40.                         stos.pop();
  41.                     }
  42.                     temp.ground = maksimum;
  43.                     stos.push(temp);
  44.                 }
  45.             }
  46.             if(hightestPoint < stos.top().height + stos.top().ground){
  47.                 hightestPoint = stos.top().height + stos.top().ground;
  48.             }
  49.         }
  50.         cout << hightestPoint << endl;
  51.     }
  52.     return 0;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment