제출 #1168602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168602		thuanphong20042009	Bank (IZhO14_bank)	C++20	25 / 100	1095 ms	540 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#define FastIO ios_base::sync_with_stdio(0);cin.tie(NULL);
#define name "fuck"
#define MULTEST int t;cin >> t;while (t--) solve();
#define minus __minus__
#define prev __prev__
#define next __next__
#define time __time__
#define start __start__
#define count __count__

int n,m,a[29],b[29];
bool dp[22][(1 << 20) + 1];
int calculate(int mask) {
    int sum = 0;
    for (int i = 1;i <= m;i++) {
        if ((mask >> (i - 1))&1) sum += b[i];
    }
    return sum;
}
int main() {
    FastIO;
    cin >> n >> m;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int j = 1;j <= m;j++) cin >> b[j];
    dp[0][0] = 1;
    for (int i = 1;i <= n;i++) {
        int target = a[i];
        for (int mask = 1;mask < (1 << m);mask++) {
            for (int submask = mask;(submask > 0) && !dp[i][mask];submask = (submask - 1)&mask) {
                if (calculate(submask) == target) dp[i][mask] |= dp[i - 1][mask - submask];
            }
        }
    }
    cout << (*max_element(dp[n] + 1,dp[n] + (1 << m)) == 1 ? "YES" : "NO");
}

/*
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------=============-----------------------------------------------------------------------------------=+*********+=----------------------------
--------------------------================--------------------------------------------------------------------------------=+++************=--------------------------
-------------------------================++=-----------------------------------------------------------------------------=+++++************=-------------------------
------------------------=============+++++++=---------------------------------------------------------------------------=++++++*************=------------------------
------------------------=======+++++++++++++=-------------------------------=============-------------------------------=+++++++************+------------------------
------------------------===+++++++++++++++++=--------------------------=+++++++++++++++++++++=--------------------------++++++++************+------------------------
--------------========++=+++++++++++++++++++=+++++++++=-----------=++++++++++++++++++++++++++++++==-----------=+++++++++=++++++++***********+*********=--------------
--------------===+++++++=++++++++++++++++++=++++++++++=--------=++++++++++++++++++++++++++++++++++++=---------=+++++++++=++++++++**********+=*********=--------------
--------------=++++++++++=++++++++++++++++==++++++++++=------=+++++++++++++++++++++++++++++++++++++++++=------=++++++++++=++++++++********++**********=--------------
--------------=++++++++++++=+++++++++++++=++++++++++++=----=+++++++++++++++++++++++++++++++++++++++++++++=----=++++++++++++=++++++******+=************=--------------
--------------=++++++++++++++==++++++===++++++++++++++=--=+++++++++++++++++++++++++++++++++++++++++++++++++=--=++++++++++++++==+++++++=+**************=--------------
--------------=+++++++++++++++++++++++++++++++++++++++=-+*++++++++++++++++++++++++++++++++++++++++++++++++++=-=++++++++++++++++++++*******************=--------------
--------------=+++++++++++++++++++++++++++++++++++++++=+++++++++++++++++++++++++++++++++++++++++++++++++++++++=++++++++++++++++++++*******************=--------------
--------------=+++++++++++++++++++++++++++++++++++++++*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++******************=--------------
--------------==========+++++++++++++++++++++========++++++++++++++++++++++++++++===++++++++++++++++++++++++++++========++++++++++++*********+=========--------------
-----------------------=+++++++++++++++++++++=-----=+*+++++++++++++++++++++++=---------++++++++++++++++++++++++++------=+++++++++++++********=-----------------------
-----------------------=+++++++++++++++++++++=-----=++++++++++++++++++++++++------------=++++++++++++++++++++++++=-----=+++++++++++++********=-----------------------
-----------------------=+++++++++++++++++++++=-----+++++++++++++++++******=---------------+*********************++=----=++++++++++++++*******=-----------------------
-----------------------=+++++++++++++++++++++=----=++********************+----------------=+**********************=----=*******+++++++*******=-----------------------
-----------------------=++++++++++++++++++++*=----+++********************=-----------------+***********************----=*********************=-----------------------
-----------------------=++++++++++++++++++++*=----*++*******************+------------------=***********************=---=*********************=-----------------------
-----------------------=++++++++++++++++++++*=---=*+++******************=-------------------***********************=---=*********************=-----------------------
-----------------------=++++++++++++++++++++*=---=*++++*****************=-------------------+**********************=---=*********************=-----------------------
-----------------------=++++++++++++++++++++*=---=*++++*****************=-------------------***********************=---=*********************=-----------------------
-----------------------=++++++++++++++++++++*=---=*+++++****************+------------------=***********************=---=*********************=-----------------------
-----------------------=++++++++++++++++++++*=----++++++*****************=-----------------+***********************----=*********************=-----------------------
-----------------------=++++++++++++++++++++*=----=++++++****************+----------------=***********************=----=*********************=-----------------------
-----------------------=*******+++++++++++++*=-----++++++*****************+---------------************************=----=*********************=-----------------------
-----------------------=**************++++++*=-----+++++++*****************+------------=************************+-----=*********************=-----------------------
-----------------------=*********************=-----=+++++++******************+--------=+*************************------=#********************=-----------------------
---------------=========*********************========*+++++*********************+===+***************************========#********************+========---------------
--------------=*******************************************+*******************************************************************************************=--------------
--------------=***************************************=+******************************************************=***************************************=--------------
--------------=***************************************=-+***************************************************=-=***************************************=--------------
--------------=***************************************=--=*************************************************---=***************************************=--------------
--------------=***************************************=----+*********************************************=----=***************************************=--------------
--------------=***************************************=------=*****************************************-------=***************************************=--------------
--------------=***************************************=--------=+***********************************+---------=***************************************=--------------
--------------=***************************************=------------+*****************************=------------=***************************************=--------------
---------------=======================================----------------=++*******************+==----------------=======================================---------------
-------------------------------------------------------------------------------=======-------------------------------------------------------------------------------
--------------=====----===================--==---==---==-==========--====---==---==--===--===-------====--===-==---=====----==-====--===--===--=====-----------------
--------------=+==++=--+=--++--=+=---=+-=++-++=--+=--=++=--=+=--=+==+=--++=-++=--+=-=+++=-=+=-----=+=-=++==+=-=++-=+==++---=++-++-=+==+=-=+++--=+--=++---------------
--------------=+==+=+=-+=--++--=+++=-=+=++=-++++=+=-=+==+=-=+=--=+=++----++-+=++=+=-=+=++-=+=-----+=----+==+=---+++=-=+=+=++++-++==+==+=-++-+=-=+---=+=--------------
--------------=+==+=-+++=--++--=+=---=+-=+--++-=++==++++++-=+=--=+==+=---+=-+=-=++==+++++==+=-----++=--=+==+=---=+=--=+==++-++-++----=+==+++++==+---=+=--------------
--------------=+==+=--=+=--+=--=++++==+--=+=+=--=+==+---=+==+=--=+=-=++++=--+=--=+=+=---=+=++++=---=+++==-=++++==+=--=+=-=--==-==----=+=+=---=+=++++==---------------
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------===---+=------===------===--===-----===--=========----=+++=-----=======----===--------===------===---==========-===-----==++==----=+++=----------------
--------------=**=-=***-----+*=------+*+--***=----=*+--+******+=-=*********=--=**++***+--=***------=***-----+***=--+********+==**---=********=-***+**+=--------------
--------------=**=-=****=---+*=------+*+--****+---=*+--+*+------=**=-----+**=-=**---=**=-=***+=---=****----=**+**=----=**=----=**--+**=-------+*+--------------------
--------------=**=-=*+-**+--+*=------+*+--**=+**=-=*+--+*+=====-**+------=+*+-=**---+**--=*+=*+--=**=**---=**=-+*+----=**=----=**-=**=---------****+=----------------
--------------=**=-=*+--+**=+*=------+*+--**=-=**+=*+--+**++++=-**+------=+*+-=******=---=*+-=**=**=-**---+*+===**=---=**=----=**-=**=----------==+***=--------------
--------------=**=-=*+---=****=------+*+--**=---+***+--+*+------=**=-----+**=-=**--+**=--=*+--+***=--**--+*********=--=**=----=**--+**--------------**=--------------
--------------=**=-=*+----=+**=------+*+--**=----+**+--+*+-------=***++***+=--=**---=**=-=*+---=+=---**-=**=-----+*+=-=**=----=**---=***++***=***++**+=--------------
---------------==---==------==-------==---==-------==--===----------=====------==----===--==---------==-===-------==---==------==-----=====-----====-----------------
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
*/

• Subtask 1: 0 / 19
• Subtask 2: 25 / 25
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29