QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#751219 | #8034. Ban or Pick, What's the Trick | Eqvpkbz# | WA | 0ms | 3828kb | C++17 | 2.0kb | 2024-11-15 17:33:06 | 2024-11-15 17:33:06 |
Judging History
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'