조건

Hmax=용사의 최대 생명력(1 이상이여야하고 던전 들어가고 나서부터는 안변함)
Hcurr=현재 용사의 생명력(던전 들어가기전 이 값은 용사의 최대 생명력과 같음)
Hatk=용사의 공격력

던전이 N개가 있고 i번째 방부터 i+1 번째 방으로 이동가능하다.
각각의 방은 몬스터 or 포션이 있고 몬스터를 만나면 무찔러야하고 포션먹으면 공격력과 체력이 찬다.

그리고 진행방식은 이렇게 된다.

마지막으로 Hmax가 최소로 몇이여야 던전을 통과할수 있는지 확인해야한다.

이해

사실 삼성코테를 준비했던 나는 세 종류의 능력치가 있습니다... 를 보자마자 이건 구현문제다... 했다.
실제로 조건에 맞게 구현하면 됐었는데 한가지 좀 신선했던것은 방의 개수가 1<=N<=123456 이기 떄문에
Hmax 의 최소값부터 최대값까지 하나하나 다 확인하게 되면 너무 오랜 시간이 걸리게 된다.
그래서 나는 이건 이분탐색으로 최적의 Hmax 를 찾아주려했다

조건은 당연하게 Hmax 가 됐고, 최소 조건은 1로 잡아주고 최대조건은 9e18까지 잡아주었다.
구현은 쉽게 구현하였고 해당 Hmax를 이분탐색을 통해서 찾아주면 된다.

코드

#include <iostream>
#include <vector>
using namespace std;

struct Node {
    int t,a,h;
};

vector<Node> v;
int N,H;
long long low=1,high=9e18,mid,ret;
long long temp;

int go_(long long Hp,long long Atk) {
    
    long long temp_Hp=Hp;
    for(Node temp:v) {
        
        if(temp.t==1) {
            if(temp.h%Atk) {
                temp_Hp-=(temp.h/Atk)*temp.a;
            }
            else {
                temp_Hp-=(temp.h/Atk-1)*temp.a;
            }
//            cout << temp_Hp << "\n";
//            cout << temp.h << " " << Atk << " " << temp.a << "\n";
            if(temp_Hp<=0) {
                return 0;
            }
        }
        else {
            Atk+=temp.a;
            temp_Hp+=temp.h;
            if(temp_Hp>Hp) {
                temp_Hp=Hp;
            }
        }
    }
    
    
    return 1;
}

void start() {
    
    while(low<=high) {
        mid=(low+high)/2;
//        cout << mid << "\n";
        
        if(go_(mid,H)) {
//            cout << mid << "\n";
            ret=mid;
            high=mid-1;
        }
        else {
            low=mid+1;
        }
    }
    
    cout << ret << "\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> N >> H;
    temp=H;
    for(int i=0;i<N;i++) {
        int t,a,h;
        cin >> t >> a >> h;
        v.push_back({t,a,h});
    }
    
    start();
    
    return 0;
}