QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#559541 | #6194. Knapsack Problem | pandapythoner# | WA | 683ms | 3592kb | C++23 | 2.3kb | 2024-09-11 22:59:55 | 2024-09-11 22:59:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define len(a) ((int)(a).size())
#define rep(i, n) for(int i = 0; i < (n); i += 1)
mt19937 rnd(234);
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int t;
cin >> t;
rep(itr, t) {
int k;
cin >> k;
vector<ll> c(1 << k);
c[0] = 0;
ll mxc = 0;
for (int i = 1; i < (1 << k); i += 1) {
cin >> c[i];
mxc = max(mxc, c[i]);
}
vector<ll> a(k);
rep(i, k) cin >> a[i];
function<ll(array<ll, 4>&, int)> get;
get = [&](array<ll, 4>& cur, int i) -> ll {
if (i == k) return 0;
ll mn = c[(1 << i)];
for (int mask = 1; mask < (1 << i); mask += 1) {
ll sum = 0;
rep(j, i) {
if ((mask >> j) & 1) {
sum += cur[j];
}
}
mn = max(mn, c[mask | (1 << i)] - sum);
}
if (i == k - 1) {
return mn * a[i];
}
ll tl = mn;
ll tr = 4e9 + 100;
while (tl + 10 < tr) {
ll tm1 = (tl + tr) / 2;
ll tm2 = tm1 + 1;
cur[i] = tm1;
ll val1 = a[i] * tm1 + get(cur, i + 1);
cur[i] = tm2;
ll val2 = a[i] * tm2 + get(cur, i + 1);
if (val1 <= val2) {
tr = tm2;
} else {
tl = tm1;
}
}
ll result = 8e18;
for (ll x = tl; x <= tr; x += 1) {
cur[i] = x;
result = min(result, a[i] * x + get(cur, i + 1));
}
return result;
};
array<ll, 4> cur;
ll result = get(cur, 0);
cout << result << "\n";
}
return 0;
}
/*
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 20746781
*/
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 3592kb
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
Wrong Answer
time: 683ms
memory: 3520kb
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...
output:
16156444320083421 24565535429631234 29418802996321901 30685727712782520 21026118053726857 27272339796311010 28831028447377015 34577176834491138 9058894962996375 21525085254465501 6657186892229297 16750628911275484 11217846865301187 12674726744043780 33873234230125448 3890237279573366 319038768614465...
result:
wrong answer 8th numbers differ - expected: '34577176834491128', found: '34577176834491138'