Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define _in(kkk) 2*(kkk) - 1
- #define _out(kkk) 2*(kkk)
- using namespace std;
- typedef unsigned long long int llu;
- vector<vector<llu> > res;
- llu mf, f, s, t, k, m, size;
- vector<llu> parent;
- void augument(llu v, llu minEdge)
- {
- if(v == s)
- {
- f = minEdge;
- return;
- }
- if(parent[v] != -1) {
- augument(parent[v], min(minEdge, res[parent[v]][v]));
- res[parent[v]][v] -= f;
- res[v][parent[v]] += f;
- }
- }
- void init(const vector<llu>& a, const vector<llu>& b)
- {
- size = 2*(a.size() + b.size()) + 2;
- res.assign(size, vector<llu>(size, 0));
- for(llu i = 1; i <= a.size(); ++i)
- res[_in(i)][_out(i)] = 1;
- for(llu i = 1; i <= b.size(); ++i)
- res[_in(a.size() + i)][_out(a.size() + i)] = 1;
- for(llu i = 1; i <= a.size(); ++i)
- for(llu j = 1; j <= b.size(); ++j)
- if(max(a[i-1], b[j-1]) - min(a[i-1], b[j-1]) < k)
- res[_out(i)][_in(a.size() + j)] = res[_out(a.size() + j)][_in(i)] = 1;
- s = 0; t = size - 1;
- for(llu i = 1; i <= m; ++i)
- res[s][_in(i)] = 1;
- for(llu i = a.size() + b.size(); i > a.size() + b.size() - m; --i)
- res[_out(i)][t] = 1;
- }
- llu maxFlow(const vector<llu>& a, const vector<llu>& b)
- {
- init(a,b);
- mf = 0;
- while(1)
- {
- f = 0;
- vector<bool> saw(size, false);
- queue<llu> fila;
- saw[s] = true; fila.push(s);
- parent.assign(size, -1);
- while(!fila.empty())
- {
- llu u = fila.front(); fila.pop();
- if(u == t) break;
- for(llu v = 0; v < size; ++v)
- if(res[u][v] && !saw[v])
- {
- saw[v] = true;
- fila.push(v);
- parent[v] = u;
- }
- }
- augument(t, ULLONG_MAX);
- if(!f) break;
- mf += f;
- }
- return mf;
- }
- int main()
- {
- llu na, nb;
- scanf("%llu %llu %llu %llu", &m, &na, &nb, &k);
- vector<llu> a(na), b(nb);
- for(llu i = 0; i < na; ++i)
- scanf("%llu", &a[i]);
- for(llu i = 0; i < nb; ++i)
- scanf("%llu", &b[i]);
- sort(b.rbegin(), b.rend());
- sort(a.rbegin(), a.rend());
- llu an = maxFlow(a,b);
- if(an < m)
- an = maxFlow(b,a);
- if(an >= m)
- puts("S");
- else
- puts("N");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement