BOJ 25055

2차원에서 생각해 보면 저 두 그래프의 오른쪽에 있을 경우에만 이동할 수 있다. 기울기가 모두 같기 때문에 기울기가 양수인 그래프의 경우 y절편이 감소해야 하며, 기울기가 음수인 그래프의 경우 y절편이 증가해야 한다. 따라서 기울기가 양수인 경우를 내림차순 정렬한 후, LIS를 구하면 된다. 단, 불가능한 경우를 제외해 줘야 한다.

 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

inline void init() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

int main() {
    init();

    ll n, v;

    cin >> n >> v;

    vector<ll> t(n), a(n);

    for (auto& x : t) cin >> x;
    for (auto& x : a) cin >> x;

    vector<pll> p(n);

    for (ll i = 0; i < n; i++) {
        p[i] = {a[i] - v * t[i], a[i] + v * t[i]};
    }

    sort(p.begin(), p.end(), [&](pll a, pll b) -> bool {
        return a.first == b.first ? a.second < b.second : a.first > b.first;
    });

    vector<ll> ans;

    for (auto& [x, y] : p) {
        if (x > 0 or y < 0) continue;

        if (ans.empty() or ans.back() <= y) {
            ans.emplace_back(y);
        } else {
            *upper_bound(ans.begin(), ans.end(), y) = y;
        }
    }

    cout << ans.size();

    return 0;
}