60pts,剩余RE
查看原帖
60pts,剩余RE
402384
orgn楼主2023/10/11 20:16

以为是开小了,但是好像没有影响

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXX 105
ll n,m,a[MAXX],len1,len2,ans=0x7fffffff;
struct node{ ll num,cnt; }s1[1<<21],s2[1<<21];
inline ll read();
void dfs(ll x,ll y,ll now,ll sum){
    if(now>ans) return;
    if(x==y){
        if(y==n/2+1)
            s1[++len1].num=now,s1[len1].cnt=sum;
        if(y==n+1)
            s2[++len2].num=now,s2[len2].cnt=sum;
        return;
    }
    dfs(x+1,y,now,sum);
    dfs(x+1,y,now,sum+a[x]);
    dfs(x+1,y,now+1,sum+a[x]/2);
    return;
}
bool cmp1(node a,node b){ return a.cnt<b.cnt; }
bool cmp2(node a,node b){ return a.cnt>b.cnt; }
int main (){
    n=read(),m=read()*2;
    for(ll i=1;i<=n;i++) a[i]=read()*2;
    sort(a+1,a+1+n);
    dfs(1,n/2+1,0,0),dfs(n/2+1,n+1,0,0);
    sort(s1+1,s1+1+len1,cmp1);
    sort(s2+1,s2+1+len2,cmp2);
    ll l=1,r=1;
    while(l<=len1 && r<=len2){
        while(s1[l].cnt+s2[r].cnt>m && r<=len2) r++;
        ll qwer=r;
        while(s1[l].cnt+s2[r].cnt==m && r<=len2)
            ans=min(ans,s1[l].num+s2[r].num),r++;
        if(l<len1 && s1[l].cnt==s1[l+1].cnt) r=qwer;
        l++;
    } 
    if(ans>998244353) cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}
inline ll read(){
    ll k=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0' && ch<='9') k=k*10+ch-'0',ch=getchar();
    return k*f;
}
2023/10/11 20:16
加载中...