QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#751219#8034. Ban or Pick, What's the TrickEqvpkbz#WA 0ms3828kbC++172.0kb2024-11-15 17:33:062024-11-15 17:33:06

Judging History

This is the latest submission verdict.

  • [2024-11-15 17:33:06]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3828kb
  • [2024-11-15 17:33:06]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
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>());
    
    int lim = 2 * n, up = min(k, n);
    const int INF = 0x3f3f3f3f3f3f3f3fll;
    
    vector<vector<vector<int> > > f(lim + 2, vector<vector<int> > (up + 2, vector<int>(k + 2)));
    vector<vector<vector<bool> > > vis(lim + 2, vector<vector<bool> > (up + 2, vector<bool>(k + 2)));
    
    auto dfs = [&](auto self, int i, int A, int B) -> int {
        if (i > lim) return 0;
        
        int illegal = (i & 1) ? -INF : INF, tim = ((i - 1) / 2) + ((i & 1) == 0); 
        
        if (((i & 1) && (tim - B + A) > n) || (!(i & 1) && (tim - A + B) > n)) return illegal;
        
        if (vis[i][A][B]) return f[i][A][B]; 
        vis[i][A][B] = true; 
        f[i][A][B] = illegal;
        
        if ((i & 1) && (tim - B + A) < n && A + 1 <= up) f[i][A][B] = self(self, i + 1, A + 1, B) + a[tim - B + A];
        if (!(i & 1) && (tim - A + B) < n && B + 1 <= up) f[i][A][B] = self(self, i + 1, A, B + 1) - b[tim - A + B];
        if (i & 1) return f[i][A][B] = max(f[i][A][B], self(self, i + 1, A, B));
        else return f[i][A][B] = min(f[i][A][B], self(self, i + 1, A, B));
    };
    cout << dfs(dfs, 1, 0, 0) << "\n";
    // for(int i = 1; i <= lim; ++ i)
    //     for(int A = 0; A <= up; ++ A)
    //         for(int B = 0; B <= up; ++ B) {
    //             if (!vis[i][A][B]) cerr << " --- ";
    //             cerr << "Find : " << i << " " << A << " " << B << " | " << vis[i][A][B] << " | " << f[i][A][B] << "\n";
    //         }
    return;
}
signed main() {
    ios::sync_with_stdio(false);
    cout.tie(0), cin.tie(0);
    int T = 1;
    // cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3796kb

input:

2 1
3 6
2 4

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

4 1
1 3 5 7
2 4 6 8

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

4 2
4 6 7 9
2 5 8 10

output:

3

result:

ok single line: '3'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3520kb

input:

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

output:

40

result:

wrong answer 1st lines differ - expected: '41', found: '40'