QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#743484	#8034. Ban or Pick, What's the Trick	ucup-team3548^#	TL	1ms	3848kb	C++20	2.7kb	2024-11-13 19:20:11	2024-11-13 19:20:15

Judging History

This is the latest submission verdict.

[2024-11-13 19:20:15]
Judged

Verdict: TL
Time: 1ms
Memory: 3848kb

Show

[2024-11-13 19:20:11]
Submitted

answer

#include <bits/stdc++.h>

using namespace std;

const int inf = 2e9 + 7;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }
    sort(a.begin(), a.end(), greater<int> ());
    sort(b.begin(), b.end(), greater<int> ());
    // vector<int> f(k + 1, -2000000000), g(k + 1, 2000000000);
    vector<vector<vector<int> > > f(2 * n + 1, vector<vector<int> > (k + 1, vector<int>(k + 1, -inf)));
    auto dfs = [&](auto &&self, int r, int k1, int k2) ->int {
        if (r > 2 * n) return 0;
        if (f[r][k1][k2] != -inf) {
            return f[r][k1][k2];
        }
        if (r & 1) {
            if (k1 == 0) {
                return self(self, r + 1, k1, k2);
            }
            int x = k2 - k1 + r / 2;
            int res = max(self(self, r + 1, k1 - 1, k2) + (x < n ? a[x] : 0), self(self, r + 1, k1, k2));
            return f[r][k1][k2] = res;
        } else {
            if (k2 == 0) {
                return self(self, r + 1, k1, k2);
            }
            int x = k1 - k2 + r / 2;
            int res = min(self(self, r + 1, k1, k2 - 1) - (x < n ? b[x] : 0), self(self, r + 1, k1, k2));
            return f[r][k1][k2] = res;
        }
    };
    cout << dfs(dfs, 1, k, k) << "\n";
    // f[0] = g[0] = 0;
    // for (int i = 0; i < n; ++i) {
    //     for (int j = 0; j <= min(i + 1, k); ++j) {
    //         for (int l = min(i + 1, k); l >= 0; --l) {
    //             f[j][l] =  
    //         }
    //     }
        // f[0] = *min_element(g.begin(), g.end());
        // for (int j = 1; j <= min(i + 1, k); ++j) {
        //     f[j] = g[0] + (i + j - 1 < n ? a[i + j - 1] : 0);
        //     for (int l = 1; l <= min(i, k); ++l) {
        //         f[j] = min(f[j], g[l] + (i - l + j - 1 < n ? a[i - l + j - 1] : 0));
        //     }
        // }
        // g[0] = *max_element(f.begin(), f.end());
        // for (int j = 1; j <= min(i + 1, k); ++j) {
        //     g[j] = f[0] + (i + j < n ? b[i + j] : 0);
        //     for (int l = 1; l <= min(i + 1, k); ++l) {
        //         g[j] = max(g[j], f[l] - (i - l + j < n ? b[i - l + j] : 0));
        //     }
        // }
        // for (int i = 0; i <= k; ++i) {
        //     cout << i << " " << f[i] << "\n";
        // }
        // for (int i = 0; i <= k; ++i) {
        //     cout << i << " " << g[i] << "\n";
        // }
    // }
    // cout << *min_element(g.begin(), g.end()) << "\n";
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3560kb

input:

2 1
3 6
2 4

output:

result:

ok single line: '2'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3548kb

input:

4 1
1 3 5 7
2 4 6 8

output:

result:

ok single line: '0'

Test #3:

score: 0

Accepted

time: 0ms

memory: 3848kb

input:

4 2
4 6 7 9
2 5 8 10

output:

result:

ok single line: '3'

Test #4:

score: 0

Accepted

time: 0ms

memory: 3592kb

input:

10 5
42 13 60 42 100 82 22 98 14 55
100 41 89 24 65 38 69 26 37 16

output:

result:

ok single line: '41'

Test #5:

score: 0

Accepted

time: 0ms

memory: 3800kb

input:

9 10
4 32 566 885 439 479 332 95 432
409 140 704 26 558 781 457 356 404

output:

result:

ok single line: '58'

Test #6:

score: 0

Accepted

time: 0ms

memory: 3616kb

input:

20 8
249 888 548 338 840 890 519 416 852 817 28 694 271 947 239 11 654 914 765 939
483 148 403 552 250 635 287 644 364 822 621 151 31 422 683 959 867 266 837 395

output:

result:

ok single line: '1201'

Test #7:

score: 0

Accepted

time: 1ms

memory: 3760kb

input:

100 10
9813 7151 1299 6277 9002 7359 770 1582 3909 9113 1937 3436 846 9841 3378 5437 9443 9148 6862 6832 1910 1365 1328 26 7245 9468 6087 5828 8993 3378 6200 7242 6495 6783 7275 9837 5162 2140 3721 1586 7559 3721 9268 7186 1615 6648 5631 5752 3712 7856 7938 5414 9197 5259 3319 3616 3257 5880 2448 74...

output:

result:

ok single line: '2174'

Test #8:

score: -100

Time Limit Exceeded

input:

40000 5
19274618 29347041 40087005 4241769 41812959 94623872 30100813 76644033 64979494 96963240 48832843 15280489 52008818 47041532 58608992 73517436 15625815 32168369 68934604 89208811 79580765 42310673 69912065 59918072 29961600 96203768 8736038 83397821 69327027 17923674 3664021 44005027 7651388...