QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #756518 | #8034. Ban or Pick, What's the Trick | ryh7 | WA | 1ms | 7720kb | C++17 | 1.6kb | 2024-11-16 20:47:47 | 2024-11-16 20:47:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using VI = vector<int>;
using PII = pair<int,int>;
using VVI = vector<vector<int>>;
const ll mod = 998244353;
const ll INF = 1e18;
const int N = 2e5 + 10;
void solve(){
}
ll aa[N];
ll bb[N];
ll vis[N][20][20];
ll dp[N][20][20];
int n,m;
ll dfs(int now , int a , int b , int i , int j){
if(a == m && b == m) return 0;
if(now == 2 * n + 1) return 0;
if(vis[now][a][b]) return dp[now][a][b];
vis[now][a][b] = 1;
if(now % 2 == 1){
ll &r = dp[now][a][b];
if(j <= n) {
r = max(r , dfs(now + 1 , a , b , i , j + 1) );
}
if(i <= n && a + 1 <= m){
r = max(r , dfs(now + 1 , a + 1 , b , i + 1 , j) + aa[i]);
}
}else{
ll &r = dp[now][a][b];
r = 1e10;
if(i <= n) {
r = min(r , dfs(now + 1 , a , b , i + 1 , j));
}
if(j <= n && b + 1 <= m){
r = min(r , dfs(now + 1 , a , b + 1 , i , j + 1) - bb[j]);
}
}
return dp[now][a][b];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//int T;cin>>T;while(T--)solve();
//dp[i][j][k] = dp[i - 1][j][k]
//A 选了 j 个 ， 办了 i-j 个
//B 选了 k 个 ， 办了 i-k 个
//f[i][j][k] 第 i 次 A 操作后的最大分数
//g[i][j][k] 第 i 次 B 操作后的最小分数
cin>>n>>m;
for(int i = 1 ; i <= n ; i++) cin>>aa[i];
for(int i = 1 ; i <= n ; i++) cin>>bb[i];
sort(aa + 1 , aa + 1 + n , greater());
sort(bb + 1 , bb + 1 + n , greater());
cout<<dfs(1 , 0 , 0 , 1 , 1);
}
//5 4 3 2 1
//5 4 3 2 1
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5632kb
input:
2 1 3 6 2 4
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5652kb
input:
4 1 1 3 5 7 2 4 6 8
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 1ms
memory: 7720kb
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: 1ms
memory: 5808kb
input:
10 5 42 13 60 42 100 82 22 98 14 55 100 41 89 24 65 38 69 26 37 16
output:
45
result:
wrong answer 1st lines differ - expected: '41', found: '45'