Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stack>
- using namespace std;
- struct Bucket{
- public:
- int height;
- int radius;
- int ground;
- };
- int main()
- {
- int ile;
- cin >> ile;
- for(int c = 0; c < ile; c++){
- stack<Bucket> tower;
- int hightestPoint = 0;
- int bucketCount;
- cin >> bucketCount;
- Bucket temp;
- Bucket temporary; //Used to speed up a bit
- int maksimum;
- int sum;
- int counter = 0; //Its size of the Stack. Used it because thought its faster then empty() function
- for(int i = 0; i < bucketCount; i++){
- cin >> temp.radius >> temp.height;
- maksimum = -1;
- sum = 0;
- if(counter == 0){
- temp.ground = 0;
- tower.push(temp);
- counter++;
- } else {
- if(temp.radius < tower.top().radius){ //If bucket is narrower then push it
- temp.ground = tower.top().ground;
- tower.push(temp);
- counter++;
- } else { //If bucket is wider
- while((counter > 0) && temp.radius >= (temporary = tower.top()).radius){ //Pop and search for new ground (maximum)
- sum = temporary.height + temporary.ground;
- if(maksimum < sum){
- maksimum = sum;
- }
- tower.pop();
- counter--;
- }
- temp.ground = maksimum; //Set ground for new bucket
- tower.push(temp);
- counter++;
- }
- }
- sum = temp.height + temp.ground; //Meantime find highest point in stack
- if(hightestPoint < sum){
- hightestPoint = sum;
- }
- }
- cout << hightestPoint << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment