結果

問題 No.1538 引きこもりさんは引き算が得意。
ユーザー hiro71687k
提出日時 2023-03-30 20:43:05
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,083 bytes
コンパイル時間 3,929 ms
コンパイル使用メモリ 260,272 KB
最終ジャッジ日時 2025-02-11 19:17:32
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
using ld=long double;
ld pie=3.141592653589793;
ll mod=1000000007;
ll inf=9999999999999999;
int main(){
    ll n,k;
    cin >> n >> k;
    vector<ll>a(n);
    for (ll i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (ll i = 0; i < n; i++)
    {
        if (a[i]==k)
        {
            cout << "Yes" << endl;
            return 0;
        }
    }
    sort(a.begin(),a.end());
    vector<ll>thr(21,1);
    for (ll i = 1; i < 21; i++)
    {
        thr[i]=thr[i-1]*3;
    }
    if (n>10)
    {
        map<ll,ll>memo1;
        for (ll i = 0; i < 10; i++)
        {
            memo1[a[i]]=1;
        }
        ll d=n-10;
        for (ll i = 0; i < thr[10]; i++)
        {
            ll now=0;
            vector<ll>z(3,0);
            for (ll j = 0; j <10 ; j++)
            {
                ll x=i%thr[j+1];
                x/=thr[j];
                if (x==0)
                {
                    now+=a[j];
                }else if (x==1)
                {
                    now-=a[j];
                }
                z[x]+=1;
            }
            if (z[0]==0||z[1]==0)
            {
                continue;
            }
            memo1[now]+=1;
        }
        map<ll,ll>memo2;
        for (ll i = 0; i < d; i++)
        {
            memo2[a[10+i]]=1;
        }
        for (ll i = 0; i < thr[d]; i++)
        {
            ll now=0;
            vector<ll>z(3,0);
            for (ll j = 0; j <d ; j++)
            {
                ll x=i%thr[j+1];
                x/=thr[j];
                if (x==0)
                {
                    now+=a[j+10];
                }else if (x==1)
                {
                    now-=a[j+10];
                }
                z[x]+=1;
            }
            if (z[0]==0||z[1]==0)
            {
                continue;
            }
            memo2[now]+=1;
        }
        for(auto v:memo1){
            if (memo2[k+v.first]>=1||memo2[v.first-k]>=1)
            {
                cout << v.first << endl;
                cout << "Yes" << endl;
                return 0;
            }
        }
        if (memo1[k]>=1||memo2[k]>=1)
        {
            cout << "Yes" << endl;
            return 0;
        }
        cout << "No" << endl;
    }else{
        map<ll,ll>memo1;
        for (ll i = 0; i < thr[n]; i++)
        {
            ll now=0;
            vector<ll>z(3,0);
            for (ll j = 0; j <n ; j++)
            {
                ll x=i%thr[j+1];
                x/=thr[j];
                if (x==0)
                {
                    now+=a[j];
                }else if (x==1)
                {
                    now-=a[j];
                }
                z[x]+=1;
            }
            if (z[0]==0||z[1]==0)
            {
                continue;
            }
            memo1[now]+=1;
        }
        if (memo1[k]>=1)
        {
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
        
    }
    
}
0