QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#524403	#8034. Ban or Pick, What's the Trick	MCdyc	TL	2ms	5776kb	C++14	2.3kb	2024-08-19 17:12:21	2024-08-19 17:12:21

Judging History

This is the latest submission verdict.

[2024-08-19 17:12:21]
Judged

Verdict: TL
Time: 2ms
Memory: 5776kb

Show

[2024-08-19 17:12:21]
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) 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); 
        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) 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); 
        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;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 5644kb

input:

2 1
3 6
2 4

output:

result:

ok single line: '2'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3668kb

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

input:

4 2
4 6 7 9
2 5 8 10

output:

result:

ok single line: '3'

Test #4:

score: 0

Accepted

time: 2ms

memory: 5776kb

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

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

Time Limit Exceeded

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