Submission #698117

#	Time	Username	Problem	Language	Result	Execution time	Memory
698117		ToroTN	Bank (IZhO14_bank)	C++14	100 / 100	85 ms	9036 KiB

bank

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n,m,a[25],b[25],pre;
pair<int,int> dp[1100005];
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    for(int i=0;i<=1100005;i++)
    {
        dp[i]={-1e9,-1e9};
    }
    dp[0]={0,0};
    cin >> n >> m;
    for(int i=1;i<=n;i++)cin >> a[i];
    for(int i=1;i<=m;i++)cin >> b[i-1];
    for(int i=0;i<(1<<m);i++)
    {
        for(int j=0;j<m;j++)
        {
            if((i&(1<<j))==0)continue;
            pre=(i^(1<<j));
            if(dp[pre].Y+b[j]==a[dp[pre].X+1])
            {
                if(dp[pre].X+1>dp[i].X)
                {
                    dp[i]={dp[pre].X+1,0};
                }
            }else
            {
                if(dp[pre].X>dp[i].X)
                {
                    dp[i]={dp[pre].X,dp[pre].Y+b[j]};
                }
            }
        }
    }
    // for(int i=0;i<(1<<m);i++)
    // {
    //     printf("%d %d %d\n",i,dp[i].X,dp[i].Y);
    // }
    if(dp[(1<<m)-1].X==n)
    {
        printf("YES\n");
    }else
    {
        printf("NO\n");
    }
}

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