QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#524406	#8034. Ban or Pick, What's the Trick	MCdyc	WA	4ms	5700kb	C++14	2.4kb	2024-08-19 17:13:02	2024-08-19 17:13:03

Judging History

This is the latest submission verdict.

[2024-08-19 17:13:03]
Judged

Verdict: WA
Time: 4ms
Memory: 5700kb

Show

[2024-08-19 17:13:02]
Submitted

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 2e18;
const int N=2e5+5;
int n,m,k;
int arr[N],brr[N];
int ans;
int dfs(int x,int y,int k1,int k2,bool f,int curA,int curB,int dep){
    if(dep==2*n) return curA-curB;
    //int ans;
    // if(f) ans = -INF;
    // else ans = INF;
    if(f)
    {
        if(!k1||x>n||arr[x]<brr[y]) return dfs(x,y+1,k1,k2,!f,curA,curB,dep+1);
        if(y>n) return dfs(x+1,y,k1-1,k2,!f,curA+arr[x],curB,dep+1); 
        if(arr[x]>=brr[y]) return max(dfs(x,y+1,k1,k2,!f,curA,curB,dep+1),dfs(x+1,y,k1-1,k2,!f,curA+arr[x],curB,dep+1));
        // if(x>n){
        //     ans = max(ans,dfs(x,y+1,k1,k2,!f,curA,curB,dep+1));
        // }else if(y>n){
        //    if(k1) ans = max(ans,dfs(x+1,y,k1-1,k2,!f,curA+arr[x],curB,dep+1));
        // }else{
        //     if(arr[x]>=brr[y]){
        //         ans = max(ans,dfs(x,y+1,k1,k2,!f,curA,curB,dep+1));
        //     if(k1){
        //         ans = max(ans,dfs(x+1,y,k1-1,k2,!f,curA+arr[x],curB,dep+1));
        //     }
        // }else{
        //     ans = max(ans,dfs(x,y+1,k1,k2,!f,curA,curB,dep+1));
        // }
        // }
    }else
    {
        if(!k2||y>n||arr[x]>brr[y]) return dfs(x+1,y,k1,k2,!f,curA,curB,dep+1);
        if(x>n) return dfs(x,y+1,k1,k2-1,!f,curA,curB+brr[y],dep+1); 
        if(arr[x]<=brr[y]) return min(dfs(x+1,y,k1,k2,!f,curA,curB,dep+1),dfs(x,y+1,k1,k2-1,!f,curA,curB+brr[y],dep+1));
        // if(x>n){    
        //    if(k2) ans = min(ans,dfs(x,y+1,k1,k2-1,!f,curA,curB+brr[y],dep+1));
        // }else if(y>n){
        //     ans = min(ans,dfs(x+1,y,k1,k2,!f,curA,curB,dep+1));
        // }else{
        //     if(arr[x]<=brr[y]){
        //          ans = min(ans,dfs(x+1,y,k1,k2,!f,curA,curB,dep+1)); 
        //     if(k2){
        //         ans = min(ans,dfs(x,y+1,k1,k2-1,!f,curA,curB+brr[y],dep+1));
        //     } 
        // }else{
        //     ans = min(ans,dfs(x+1,y,k1,k2,!f,curA,curB,dep+1));  
        //     }  
        // }
    }
    //return 0;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    for(int i=1;i<=n;i++){
        cin>>brr[i];
    }
    sort(arr+1,arr+n+1,greater<>{});
    sort(brr+1,brr+n+1,greater<>{});
    cout<<dfs(1,1,k,k,true,0,0,0)<<"\n";
    return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3580kb

input:

2 1
3 6
2 4

output:

result:

ok single line: '2'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3636kb

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: 3564kb

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: 3652kb

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: 1ms

memory: 5700kb

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: -100

Wrong Answer

time: 4ms

memory: 5604kb

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:

wrong answer 1st lines differ - expected: '1201', found: '1326'