Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stack>
- using namespace std;
- class Bucket{
- public:
- int height;
- int radius;
- int ground;
- };
- int main()
- {
- int ile;
- cin >> ile;
- for(int p = 0; p < ile; p++){
- stack<Bucket> stos;
- int hightestPoint = 0;
- int bucketCount;
- cin >> bucketCount;
- for(int i = 0; i < bucketCount; i++){
- Bucket temp;
- cin >> temp.radius >> temp.height;
- if(stos.empty()){
- temp.ground = 0;
- stos.push(temp);
- } else {
- if(temp.radius < stos.top().radius){ //Jezeli wiadro jest wezsze to
- temp.ground = stos.top().ground;
- stos.push(temp);
- } else { //Szersze (szukamy maksimum z wezszych wiader)
- int maksimum = -1;
- while(!stos.empty() && temp.radius >= stos.top().radius){ //Dopoki wiadro ktore trzymamy jest szersze od tych ze stosu
- if(maksimum < stos.top().height + stos.top().ground){
- maksimum = stos.top().height + stos.top().ground; //znalezlismy nowego maksa
- }
- stos.pop();
- }
- temp.ground = maksimum;
- stos.push(temp);
- }
- }
- if(hightestPoint < stos.top().height + stos.top().ground){
- hightestPoint = stos.top().height + stos.top().ground;
- }
- }
- cout << hightestPoint << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment