QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#559541#6194. Knapsack Problempandapythoner#WA 683ms3592kbC++232.3kb2024-09-11 22:59:552024-09-11 22:59:55

Judging History

你现在查看的是最新测评结果

  • [2024-09-11 22:59:55]
  • 评测
  • 测评结果:WA
  • 用时:683ms
  • 内存:3592kb
  • [2024-09-11 22:59:55]
  • 提交

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'