Subtask 1:

Duyệt nhị phân để thử từng kết quả.

Độ phức tạp ~O(2^n)~

Subtask 2:

Ta sử dụng phương pháp duyệt chia đôi tập.

Ta chia ~n~ phần tử ra làm ~2~ tập phân biệt:

• Tập hợp ~A~ có ~\frac{n}{2}~ phần tử đầu tiên.
• Tập hợp ~B~ có ~n - \frac{n}{2}~ phần tử sau đó.

Ta sẽ duyệt qua tập hợp những phần tử mình sẽ chọn trong tập A, những phần tử đấy có thể biểu diễn dưới dạng số thập phân (biểu diễn bitmask) là maskFirst.

Bây giờ nhiệm vụ của ta là chọn những phần tử ở trong tập B. Gọi những phần tử ấy là maskSecond. Ta phải có điều kiện ok(maskFirst), ok(maskSecond) và ok(maskFirst, maskSecond). Trong đó hàm ok(i) là những phần tử trong tập i không xung đột với nhau và ok(i, j) là những phần tử trong tập i không xung đột những phần tử trong tập j.

Tuy nhiên nếu ta duyệt trâu thì độ phức tạp không khác gì subtask ~1~. Do đó ta chỉ duyệt maskFirst và sẽ tìm cách tìm maskSecond tốt nhất.

Hai điều kiện ok(maskFirst) và ok(maskSecond) ta có thể dễ dàng kiểm soát bằng cách chỉ xét những tập thỏa mãn. Để kiểm soát điều kiện còn lại:

• Gọi tập hợp những phần tử trong tập ~A~ xung đột với những phần tử trong maskSecond là warMaskSecond. Để ok(maskFirst, maskSecond) thì phải có maskFirst ~\&~ warMaskSecond ~= 0~. Gọi tập hợp những phần tử trong tập ~A~ mà không thuộc maskFirst là !maskFirst. Điều kiện trên tương đương với warMaskSecond là tập con của !maskFirst.

• Do đó, ta có thể chuẩn bị trước mảng g(warMaskSecond) là tổng sức mạnh tối đa nếu tập ~B~ ta chọn maskSecond. Lưu ý: có nhiều maskSecond khác nhau, nhưng có cùng warMaskSecond. Bên cạnh đó, ở trên ta đã xác định điều kiện warMaskSecond phải là tập con của !maskFirst. Vì vậy ta phải thực hiện bước tối ưu là duyệt hết tập con submask của warMaskSecond, tìm giá trị g(submask) lớn nhất và gán f(warMaskSecond) ~=~ giá trị lớn nhất đó. Bước này sẽ tốn ~O(3^{n - \frac{n}{2}})~.

• Tổng kết: khi ta duyệt maskFirst, gọi tổng sức mạnh các phần tử trong maskFirst là S. Ta lấy đáp án tối ưu max(S + f(!maskFirst)).

Độ phức tạp: ~O(2^{\frac{n}{2}} + 3^{n - \frac{n}{2}})~.

Subtask 3:

Nhận thấy subtask ~2~ ta tốn thời gian ở bước tính mảng ~f~ từ mảng ~g~. Do đó ta sẽ tìm cách tối ưu phần này.

Nếu có tập hợp warMaskSecond, ta chỉ cần bỏ đi một phần tử bất kì trong tập này, là ta lợi dụng được mảng ~f~ từ các bước tính trước. Công thức: f(warMaskSecond) = max(g(warMaskSecond), max(f(warMaskSecond ^ (2^i)))).

Độ phức tạp: ~O(2^\frac{n}{2})~

Code mẫu

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
const int N = 45;
const int M = 5000;
int c[N];
int u[M],v[M];
namespace sub1 {
    int con[N];
    int res = 0;
    void ql (int id, int mask, int sum) {
        if (id == n) {
            res = max (res,sum);
            return;
        } 
        ql(id+1,mask,sum);
        if ((con[id] & mask)) return;
        ql(id+1,mask | (1 << id), sum + c[id]);
    }
    void solve () {
        for (int i=1; i<=m; i++) {
            con[u[i]] |= (1 << v[i]);
            con[v[i]] |= (1 << u[i]);
        }
        ql (0,0,0);
        cout << res << '\n';
    }
}
namespace sub2 {
    int half;
    const int N = 45;
    const int M = (1 << 20);
    int conFirst[N],conSecond[N];
    int f[M],g[M];
    void ql_first(int id, int maskFirst, int maskSecond, int sum) {
        if (id == half) {
            f[maskSecond] = max (f[maskSecond],sum);
            return;
        } 
        ql_first(id+1,maskFirst,maskSecond,sum);
    //  cout << id << ' ' << conFirst[id] << ' ' << maskFirst << ' ' << maskSecond << endl; 
        if ((conFirst[id] & maskFirst)) return;
        ql_first(id+1,maskFirst |= (1 << id), maskSecond |= conSecond[id], sum + c[id]);
    }
    void ql_second (int id, int maskSecond, int sum) {
        if (id == n) {
            g[maskSecond] = sum;
            return;
        }
        ql_second(id+1,maskSecond,sum);
        if ((conSecond[id] & maskSecond)) return;
        ql_second(id+1,maskSecond | (1 << (id - half)), sum + c[id]);
    }
    void solve () {
        half = n / 2;
        for (int i=1; i<=m; i++) {
            if (u[i] < half) conFirst[v[i]] |= (1 << u[i]);
            else conSecond[v[i]] |= (1 << (u[i]-half));
            swap (u[i],v[i]);
            if (u[i] < half) conFirst[v[i]] |= (1 << u[i]);
            else conSecond[v[i]] |= (1 << (u[i]-half));
        }
        ql_first(0,0,0,0);
        ql_second(half,0,0);
        int mx = n - half;
    /*  for (int i=0; i<mx; i++) {
            for (int mask=0; mask<(1 << mx); mask++) {
                if (mask >> i & 1) g[mask] = max (g[mask], g[mask ^ (1 << i)]);
            }
        }*/
        int res = 0;
        for (int mask=0; mask < (1 << half); mask++) {
            int NewMask = (~mask) & ((1 << half) - 1);
            for (int sub = NewMask; sub > 0; sub = (sub-1) & NewMask) {
                res = max (res, f[mask] + g[sub]);
            }
            res = max (res, f[mask]);
        }
        cout << res << endl;
    }
}
namespace sub3 {
    int half;
    const int N = 45;
    const int M = (1 << 20);
    int conFirst[N],conSecond[N];
    int f[M],g[M];
    void ql_first(int id, int maskFirst, int maskSecond, int sum) {
        if (id == half) {
            f[maskSecond] = max (f[maskSecond],sum);
            return;
        } 
        ql_first(id+1,maskFirst,maskSecond,sum);
    //  cout << id << ' ' << conFirst[id] << ' ' << maskFirst << ' ' << maskSecond << endl; 
        if ((conFirst[id] & maskFirst)) return;
        ql_first(id+1,maskFirst |= (1 << id), maskSecond |= conSecond[id], sum + c[id]);
    }
    void ql_second (int id, int maskSecond, int sum) {
        if (id == n) {
            g[maskSecond] = sum;
            return;
        }
        ql_second(id+1,maskSecond,sum);
        if ((conSecond[id] & maskSecond)) return;
        ql_second(id+1,maskSecond | (1 << (id - half)), sum + c[id]);
    }
    void solve () {
        half = n / 2;
        for (int i=1; i<=m; i++) {
            if (u[i] < half) conFirst[v[i]] |= (1 << u[i]);
            else conSecond[v[i]] |= (1 << (u[i]-half));
            swap (u[i],v[i]);
            if (u[i] < half) conFirst[v[i]] |= (1 << u[i]);
            else conSecond[v[i]] |= (1 << (u[i]-half));
        }
        ql_first(0,0,0,0);
        ql_second(half,0,0);
        int mx = n - half;
        for (int i=0; i<mx; i++) {
            for (int mask=0; mask<(1 << mx); mask++) {
                if (mask >> i & 1) g[mask] = max (g[mask], g[mask ^ (1 << i)]);
            }
        }
        int res = 0;
        for (int mask=0; mask < (1 << mx); mask++) {
            int NewMask = (~mask) & ((1 << mx) - 1);
            res = max (res, f[mask] + g[NewMask]);
        }
        cout << res << endl;
    }
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i=0; i<n; i++) cin >> c[i];
    for (int i=1; i<=m; i++) {
        cin >> u[i] >> v[i];
        u[i]--; v[i]--;
    }
//  sub1::solve();
    sub3::solve();
}