p438.ans1
======================
6

=================
p438.in2
======================
3 10 3 8
0 2 2
4 2 2
2 4 3

=================
p438.ans2
======================
IMPOSSIBLE

=================
p438.in1
======================
3 10 3 7
0 2 2
4 2 2
2 4 3

=================
statement.txt
======================
438. The Glorious Karlutka River =)
Time limit per test: 0.5 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



A group of M tourists are walking along the Karlutka river. They want to cross the river, but they couldn't find a bridge. Fortunately, there are some piles of rubbish floating in the water, and the tourists have decided to try to cross the river by jumping from one pile to another.

A tourist can move up to D meters in any direction at one jump. One jump takes exactly one second. tourists know that the river is W meters wide, and they have estimated the coordinates of rubbish piles (Xi, Yi) and the capacity of each pile (Ci, the maximum number of tourists that this pile can hold at the same time). Rubbish piles are not very large and can be represented as points. The river flows along the X axis. tourists start on the river bank at 0 by Y axis. The Y coordinate of the opposite bank is W.

tourists would like to know if they can get to the opposite bank of the river, and how long it will take.

Input
First line of input consists of four integers: number of rubbish piles N (0 ≤ N ≤ 50), number of tourists M (0 < M ≤ 50), maximum length of tourist's jump D (0 ≤ D ≤ 1000), and width of the river W (0 < W ≤ 1000) Following N lines describe the rubbish piles, each line consists of three integers: (0 < Xi < 1000, 0 < Yi < W, 0 ≤ Ci ≤ 1000) — pile coordinates and capacity.

Output
Output a single number indicating the minimal time (in seconds) in which all tourists will be able to cross the river, or the line "IMPOSSIBLE" if it is impossible to cross the river.

Example(s)
sample input
sample output
3 10 3 7
0 2 2
4 2 2
2 4 3
6

sample input
sample output
3 10 3 8
0 2 2
4 2 2
2 4 3
IMPOSSIBLE

=================
p438.cpp
======================
#include <bits/stdc++.h>
// #include <coding_library/graph/maxflow.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

template<class T>
class MaxFlow {
  private:
    struct Edge {
        T flow, cap;
        int idx, rev, to;
        Edge(int _to, int _rev, T _flow, T _cap, int _idx)
            : to(_to), rev(_rev), flow(_flow), cap(_cap), idx(_idx) {}
    };

    vector<int> dist, po;
    int n;

    bool bfs(int s, int t) {
        fill(dist.begin(), dist.end(), -1);
        fill(po.begin(), po.end(), 0);

        queue<int> q;
        q.push(s);
        dist[s] = 0;

        while(!q.empty()) {
            int u = q.front();
            q.pop();

            for(Edge e: adj[u]) {
                if(dist[e.to] == -1 && e.flow < e.cap) {
                    dist[e.to] = dist[u] + 1;
                    q.push(e.to);
                }
            }
        }
        return dist[t] != -1;
    }

    T dfs(int u, int t, T fl = INF) {
        if(u == t) {
            return fl;
        }

        for(; po[u] < (int)adj[u].size(); po[u]++) {
            auto& e = adj[u][po[u]];
            if(dist[e.to] == dist[u] + 1 && e.flow < e.cap) {
                T f = dfs(e.to, t, min(fl, e.cap - e.flow));
                e.flow += f;
                adj[e.to][e.rev].flow -= f;
                if(f > 0) {
                    return f;
                }
            }
        }

        return 0;
    }

  public:
    const static T INF = numeric_limits<T>::max();

    MaxFlow(int n = 0) { init(n); }

    vector<vector<Edge>> adj;

    void init(int _n) {
        n = _n;
        adj.assign(n + 1, {});
        dist.resize(n + 1);
        po.resize(n + 1);
    }

    void add_edge(int u, int v, T w, int idx = -1) {
        adj[u].push_back(Edge(v, adj[v].size(), 0, w, idx));
        adj[v].push_back(Edge(u, adj[u].size() - 1, 0, 0, -1));
    }

    T flow(int s, int t) {
        assert(s != t);

        T ret = 0, to_add;
        while(bfs(s, t)) {
            while((to_add = dfs(s, t))) {
                ret += to_add;
            }
        }

        return ret;
    }
};

int n, m, jump_d, w;
vector<tuple<int, int, int>> rubish;

void read() {
    cin >> n >> m >> jump_d >> w;
    rubish.resize(n);
    for(auto& [x, y, z]: rubish) {
        cin >> x >> y >> z;
    }
}

void solve() {
    if(jump_d >= w) {
        cout << 1 << '\n';
        return;
    }

    int max_ans = n + 1 + m;
    int num_vers = 2 + max_ans * 2 * n, source = num_vers - 2, sink = num_vers - 1;

    function<int(int, int, int)> encode_state = [&](int t, int i,
                                                    int in_out_flag) -> int {
        return t * 2 * n + 2 * i + in_out_flag;
    };

    MaxFlow<int> mf(num_vers);

    int flow = 0;
    for(int t = 0; t < max_ans; t++) {
        for(int i = 0; i < n; i++) {
            auto [x, y, c] = rubish[i];
            if(y <= jump_d) {
                mf.add_edge(source, encode_state(t, i, 0), MaxFlow<int>::INF);
            }
            mf.add_edge(encode_state(t, i, 0), encode_state(t, i, 1), c);
            if(y + jump_d >= w) {
                mf.add_edge(encode_state(t, i, 1), sink, MaxFlow<int>::INF);
            }

            if(t > 0) {
                for(int j = 0; j < n; j++) {
                    auto [x2, y2, _] = rubish[j];
                    if((x - x2) * 1ll * (x - x2) + (y - y2) * 1ll * (y - y2) <=
                       jump_d * 1ll * jump_d) {
                        mf.add_edge(
                            encode_state(t - 1, j, 1), encode_state(t, i, 0),
                            MaxFlow<int>::INF
                        );
                    }
                }
            }
        }

        flow += mf.flow(source, sink);
        if(flow >= m) {
            cout << t + 2 << '\n';
            return;
        }
    }

    cout << "IMPOSSIBLE\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
