Submission #1087253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087253		MrPavlito	Bank (IZhO14_bank)	C++17	100 / 100	86 ms	8540 KiB

bank

#include <bits/stdc++.h>
//#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>

using namespace std;

const int MAXN = 2e3+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;


signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--)
    {
        int n,m;cin >> n >> m;
        int M = (1<<m);
        int plate[n];
        int novac[m];
        for(int i=0; i<n; i++)cin >> plate[i];
        for(int i=0; i<m; i++)cin >> novac[i];
        vector<pii> dp(M+5, {-1,-1});
        dp[0] = {0,0};
        for(int i=0; i<M; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(i&(1<<j))
                {
                    int premask = (i^(1<<j));
                    if(dp[premask] == mp(-1,-1))continue;
                    int cntludi = dp[premask].fi;
                    int leftover = dp[premask].sc;
                    int trsum = leftover+ novac[j];
                    if(trsum == plate[cntludi])
                    {
                        dp[i].fi = cntludi+1;
                        dp[i].sc = 0;
                    }
                    if(trsum < plate[cntludi])
                    {
                        dp[i].sc = trsum;
                        dp[i].fi = cntludi;
                    }
                }
            }
            if(dp[i].fi == n)
            {
                cout << "YES" << endl;
                return 0;
            }
        }

        cout << "NO" << endl;

    }
}

/*
2 6
9 10
5 4 8 6 3 11
*/

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