Submission #35791530

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

template<typename T>
struct dinic {
    struct edge {
        int v, nxt;
        T f, c;
    };
    vector<edge> es;
    vector<int> head, cur, d;
    int n, tot;
    const T inf = numeric_limits<T>::max();
    dinic(int n): n(n) {
        cur.resize(n);
        head.resize(n);
        d.resize(n);
        fill(head.begin(), head.end(), -1);
        tot = 0;
    }
    void adde(int u, int v, T w) {
        es.push_back({v, head[u], 0, w});
        head[u] = tot++;
        es.push_back({u, head[v], 0, 0});
        head[v] = tot++;
    }
    T maxflow(int s, int t) {
        auto bfs = [&]() -> int {
            for (int i = 0; i < n; ++i)
                d[i] = -1;

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

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

                for (int i = head[u]; ~i; i = es[i].nxt) {
                    if (d[es[i].v] == -1 && es[i].f < es[i].c) {
                        d[es[i].v] = d[u] + 1;
                        q.push(es[i].v);

                        if (es[i].v == t)
                            return 1;
                    }
                }
            }

            return 0;
        };
        function<T(int, T)> dfs = [&](int u, T f) {
            if (u == t || !f)
                return f;

            T ret = 0;

            for (int &i = cur[u]; ~i; i = es[i].nxt) {
                if (d[es[i].v] == d[u] + 1 && es[i].c - es[i].f) {
                    T tmp = dfs(es[i].v, min(f, es[i].c - es[i].f));

                    if (!tmp) {
                        d[es[i].v] = 0;
                        continue;
                    }

                    es[i].f += tmp;
                    es[i ^ 1].f -= tmp;
                    f -= tmp;
                    ret += tmp;

                    if (!f)
                        break;
                }
            }

            return ret;
        };
        T ans = 0;

        while (bfs()) {
            for (int i = 0; i < n; ++i)
                cur[i] = head[i];

            ans += dfs(s, inf);
        }

        return ans;
    }
};

int main() {
    cin.tie(NULL)->ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<array<int, 2>> a(n);
    vector<array<int, 2>> one, zero;

    for (auto &[x, y] : a)
        cin >> x >> y;

    int cnt = 0;

    for (auto [x, y] : a) {
        if (x == 1) {
            cnt = y;
        } else if (x % 2 == 0) {
            zero.push_back({x, y});
        } else {
            one.push_back({x, y});
        }
    }

    auto ok = vector(zero.size(), vector(one.size(), false));

    auto isPrime = [&](int x) {
        for (int i = 2; i * i <= x; ++i) {
            if (x % i == 0)
                return false;
        }

        return true;
    };

    for (int i = 0; i < zero.size(); ++i) {
        for (int j = 0; j < one.size(); ++j) {
            if (isPrime(zero[i][0] + one[j][0])) {
                ok[i][j] = 1;
            }
        }
    }

    auto cal = [&](int x) {
        int s = 1 + zero.size() + one.size(), t = 2 + zero.size() + one.size();
        dinic<long long> g(t + 1);

        for (int i = 0; i < zero.size(); ++i) {
            g.adde(s, i, zero[i][1]);
        }

        for (int i = 0; i < one.size(); ++i) {
            g.adde(zero.size() + i, t, one[i][1]);
        }

        for (int i = 0; i < zero.size(); ++i) {
            for (int j = 0; j < one.size(); ++j) {
                if (ok[i][j])
                    g.adde(i, zero.size() + j, 1e18);
            }
        }

        for (int i = 0; i < zero.size(); ++i) {
            if (isPrime(1 + zero[i][0]))
                g.adde(i, zero.size() + one.size(), 1e18);
        }

        g.adde(zero.size() + one.size(), t, cnt - x * 2);
        auto a = g.maxflow(s, t);
        return a + x;
        return g.maxflow(s, t) + x;
    };


    int l = 0, r = cnt / 2;

    if (l == r) {
        cout << cal(0) << endl;
        return 0;
    }

    long long lans = 0, rans = 0;

    while (l < r) {
        int lmid = l + (r - l) / 3;
        int rmid = r - (r - l) / 3;
        lans = cal(lmid), rans = cal(rmid);

        if (lans >= rans)
            r = rmid - 1;
        else
            l = lmid + 1;
    }

    cout << max(lans, rans) << endl;
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:127:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::array<int, 2> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  127 |     for (int i = 0; i < zero.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~
./Main.cpp:128:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::array<int, 2> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  128 |         for (int j = 0; j < one.size(); ++j) {
      |                         ~~^~~~~~~~~~~~
./Main.cpp: In lambda function:
./Main.cpp:139:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::array<int, 2> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  139 |         for (int i = 0; i < zero.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~
./Main.cpp:143:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::array<int, 2> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  143 |         for (int i = 0; i < one.size(); ++i) {
      |                         ~~^~~~~~~~~~~~
./Main.cpp:147:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::array<int, 2> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  147 |         for (int i = 0; i < zero.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~
./Main.cpp:148:31: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::array<int, 2> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  148 |             for (int j = 0; j < one.size(); ++j) {
      |                             ~~^~~~~~~~~~~~
./Main.cpp:154:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::array<int, 2> >::size_type’ {aka ‘long unsi...

Judge Result