提出 #74587080

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<integral T> T rnd(T l, T r) {return uniform_int_distribution(l, r)(rng);}

void solve() {
    int n, m, k;
    ll t;
    cin >> n >> t >> k;
    m = n / 2;
    vector<ll> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }

    vector<pii> st(n);
    for (int i = 0; i < k; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        if (v < m) {
            st[u].first |= 1 << v;
        } else {
            st[u].second |= 1 << (v - m);
        }
        if (u < m) {
            st[v].first |= 1 << u;
        } else {
            st[v].second |= 1 << (u - m);
        }
    }
    if (n == 1) {
        cout << min(t, p[0]) << "\n";
        return;
    }

    vector<ll> a(1 << m), b(1 << (n - m));
    for (int s = 0; s < 1 << m; s++) {
        bool flag = true;
        for (int i = 0; i < m; i++) {
            if ((s >> i & 1) == 1 && (st[i].first & s) != 0 ) {
                flag = false;
                break;
            }
        }
        if (flag) {
            for (int i = 0; i < m; i++) {
                a[s] += (s >> i & 1) == 1 ? p[i] : 0;
            }
        }
    }
    for (int s = 0; s < 1 << (n - m); s++) {
        bool flag = true;
        for (int i =- 0; i < (n - m); i++) {
            if ((s >> i & 1) == 1 && (st[i + m].second & s) != 0) {
                flag = false;
                break;
            }
        }
        if (flag) {
            for (int i = 0; i < (n - m); i++) {
                b[s] += (s >> i & 1) == 1 ? p[i + m] : 0;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int s = 0; s < 1 << m; s++) {
            if (s >> i & 1) {
                a[s] = max(a[s], a[1 << i ^ s]);
            }
        }
    }

    ll ans = max(ranges::max(a), ranges::max(b));
    for (int s = 0; s < 1 << (n - m); s++) {
        if (b[s] != 0) {
            int ns = 0;
            for (int i = 0; i < n - m; i++) {
                if (s >> i & 1) {
                    ns |= st[i + m].first;
                }
            }
            ns = ((1 << m) - 1) ^ ns;
            ans = max(ans, b[s] + a[ns]);
        }
    }
    cout << min(ans, t) << "\n";
}

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

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

提出情報

ジャッジ結果