QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#114837 | #6194. Knapsack Problem | std_abs# | RE | 2ms | 3460kb | C++20 | 5.0kb | 2023-06-23 18:00:27 | 2023-06-23 18:00:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define sz(a) ((int)a.size())
const int mod = 998244353, N = 100005;
struct Simplex {
using T = long long;
static const int N = 16, M = 8;
int n, m;
int Left[M], Down[N];
T a[M][N], b[M], c[N], v, sol[N];
bool eq(T a, T b) {return a == b;}
bool ls(T a, T b) {return a < b;}
void init(int _n, int _m) {
n = _n, m = _m, v = 0;
for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) {
a[i][j] = 0;
}
for (int i = 0; i < m; ++i) {
b[i] = 0;
}
for (int i = 0; i < n; ++i) {
c[i] = sol[i] = 0;
}
}
void pivot(int x, int y) {
swap(Left[x], Down[y]);
T k = a[x][y]; a[x][y] = 1;
if (k == 0) {
return;
}
vector <int> nz;
for (int i = 0; i < n; ++i) {
a[x][i] /= k;
if (!eq(a[x][i], 0)) {
nz.pb(i);
}
}
b[x] /= k;
for (int i = 0; i < m; ++i) {
if (i == x || eq(a[i][y], 0)) {
continue;
}
k = a[i][y], a[i][y] = 0;
b[i] -= k * b[x];
for (int j : nz) {
a[i][j] -= k * a[x][j];
}
}
if (eq(c[y], 0)) {
return;
}
k = c[y], c[y] = 0, v += k * b[x];
for (int i : nz) {
c[i] -= k * a[x][i];
}
}
int solve() {
for (int i = 0; i < n; ++i) {
Down[i] = i;
}
for (int i = 0; i < m; ++i) {
Left[i] = n + i;
}
while (1) {
int x = -1, y = -1;
for (int i = 0; i < m; ++i) if (ls(b[i], 0) && (x == -1 || b[i] < b[x])) {
x = i;
}
if (x == -1) {
break;
}
for (int i = 0; i < n; ++i) if (ls(a[x][i], 0) && (y == -1 || a[x][i] < a[x][y])) {
y = i;
}
if (y == -1) return 1;
pivot(x, y);
}
while (1) {
int x = -1, y = -1;
for (int i = 0; i < n; ++i) if (ls(0, c[i]) && (y == -1 || c[i] > c[y])) {
y = i;
}
if (y == -1) {
break;
}
for (int i = 0; i < m; ++i) if (ls(0, a[i][y]) && (x == -1 || b[i] / a[i][y] < b[x] / a[x][y])) {
x = i;
}
if (x == -1) {
return 2;
}
pivot(x, y);
}
for (int i = 0; i < m; ++i) {
if (Left[i] < n) {
sol[Left[i]] = b[i];
}
}
return 0;
}
} solver;
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int t;
cin >> t;
while (t--) {
int k;
cin >> k;
int n = (1 << k) - 1;
solver.init(n, k * 2);
vector <int> c(n);
for (int i = 0; i < n; ++i) {
cin >> c[i];
solver.c[i] = c[i];
}
vector <int> a(k);
for (int i = 0; i < k; ++i) {
cin >> a[i];
for (int j = 0; j < n; ++j) {
solver.a[i * 2][j] = ((j + 1) >> i & 1 ? 1 : 0);
solver.a[i * 2 + 1][j] = ((j + 1) >> i & 1 ? -1 : 0);
solver.b[i * 2] = a[i];
solver.b[i * 2 + 1] = a[i];
}
}
int x = solver.solve();
assert(x == 0);
vector <ll> res(n);
for (int i = 0; i < n; ++i) {
res[i] = solver.sol[i];
}
ll best = 0;
for (int msk = 0; msk < 1 << n; ++msk) {
ll ans = 0;
vector <ll> sum(k);
for (int i = 0; i < n; ++i) for (int j = 0; j < k; ++j) if ((i + 1) >> j & 1) {
sum[j] += res[i] + (msk >> i & 1);
}
for (int i = 0; i < n; ++i) {
ans += (res[i] + (msk >> i & 1)) * c[i];
}
bool ok = true;
for (int i = 0; i < k; ++i) {
ok &= sum[i] == a[i];
}
if (ok) {
best = max(best, ans);
}
}
for (int msk = 0; msk < 1 << n; ++msk) {
ll ans = 0;
vector <ll> sum(k);
for (int i = 0; i < n; ++i) for (int j = 0; j < k; ++j) if ((i + 1) >> j & 1) {
sum[j] += res[i] - (msk >> i & 1);
}
for (int i = 0; i < n; ++i) {
ans += (res[i] - (msk >> i & 1)) * c[i];
}
bool ok = true;
for (int i = 0; i < k; ++i) {
ok &= sum[i] == a[i];
}
if (ok) {
best = max(best, ans);
}
}
cout << best << '\n';
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3460kb
input:
3 2 1 2 4 4 5 3 3226252 19270256 2430652 1187613 12496062 10286165 17494834 24 85 34 4 901133 6693218 13245489 14740234 16186210 11382783 19277321 3855635 16523184 10168517 16195031 971041 10303441 8395899 11618555 529321239 218214127 92942310 207467810
output:
18 1949753378 7832404777567179
result:
ok 3 number(s): "18 1949753378 7832404777567179"
Test #2:
score: -100
Dangerous Syscalls
input:
100 4 4488409 9842893 14331290 11289097 15777479 21131954 25620334 6146092 10634508 15988956 20477387 17435190 21923584 27278027 31766493 200477197 258791439 590664017 982949628 4 5484152 19851747 25335961 6555937 12039831 26407861 31891996 10897184 16381166 30749333 36233145 17453055 22937114 37304...