卡时

模板题

洛谷-P3973-[TJOI2015]线性代数

#include <iostream>
#include <cstring>
#include <ctime>
#define inf 0x3f3f3f3f
using namespace std;

const int N = 510;
int n, res = -inf;
int a[N], b[N][N], c[N], d, t[N];

void solve () {
    memset(t, 0, sizeof(t));
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
            t[j] += a[i] * b[i][j];
    d = 0;
    for (int i = 1; i <= n; ++ i)
        d += (t[i] - c[i]) * a[i];
    res = max(res, d);
}

int main () {
    srand(19260817);
    double beg = (double)clock() / CLOCKS_PER_SEC;

    cin >> n;
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
            cin >> b[i][j];
    for (int i = 1; i <= n; ++ i) cin >> c[i];
    
    for (int i = 1; i <= n; ++ i) a[i] = 1;
    while (true) {
        solve();
        a[rand() % n + 1] ^= 1;
        double end = (double)clock() / CLOCKS_PER_SEC;
        if (end - beg > 0.95) break;
    }
    cout << res << endl;
    return 0;
}