Submission #1289360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289360		aka_brofuck	Bank (IZhO14_bank)	C++20	71 / 100	1096 ms	11684 KiB

bank

/*
tom tat de bai : 
cho n nguoi , nguoi thu i can nhan a[i] tien . ngan hang hien tai co cac to tien b[j].. kiem tra xem co the dung m to tien tra 
het luong cho n nguoi hay khong 
* sub1 : chinh la dp knap sack thoi (khong co gi ca )
* sub3 : dp[i][x] kiem tra xem co the su cac tap X de tra tien cho nguoi tu 1 den i hay khong
dp[i][x] --> dp[i+1][y] neu nhu ma dam bao la tong cua phan them vao khong thuoc x, va co gia tri la bao nhieu   

*/
#include <bits/stdc++.h>
using namespace std;
#define deb cerr
#define rei(i,a,b) for(int i=a;i<=b;i++)
#define red(i,b,a) for(int i=b;i>=a;i--)
#define X first
#define Y seconds
#define TASK "bank"
const int maxn = 21;
int a[maxn],b[maxn];
int n,m;
void input(){
    cin>>n>>m;
    rei(i,1,n) cin>>a[i];
    rei(i,1,m) cin>>b[i];
}
inline int getbit(int x,int i){
    return (x>>(i-1))&1;
}
struct {
    bool check(){
        return n==1;
    }
    int val[(1<<20)];
    void sol(){     
        rei(x,1,(1<<m)-1) rei(i,1,m) if(getbit(x,i)) val[x]+=b[i];
        rei(x,1,(1<<m)-1) if(val[x]==a[1]){
            cout<<"YES";
            return ;
        } 
        cout<<"NO";
    }
}sub1;
struct {
    bool check(){
        return n<=20&&m<=14;
    }
    int dp[21][(1<<20)];
    int val[((1<<20))];
    void sol(){
        rei(x,1,(1<<m)-1) rei(i,1,m) if(getbit(x,i)) val[x]+=b[i];
        dp[0][0]=1;
        rei(i,0,n-1){
            rei(x,0,(1<<m)-1){
                int mask=((1<<m)-1)^x;
                for(int sub=mask;sub>0;sub=(sub-1)&mask){
                    int y=x|sub;
                    if(val[sub]==a[i+1]) dp[i+1][y]=max(dp[i+1][y],dp[i][x]);
                }
            }
        }
        int ok=0;
        rei(x,0,(1<<m)-1) if(dp[n][x]) ok=1;
        if(ok) cout<<"YES";
        else cout<<"NO";
    }
}sub3;
struct {
    bool check(){
        return 1;
    }
    int dp[21][(1<<20)];
    vector<int> gt[1001];
    int val[(1<<20)];
    void sol(){
        rei(x,1,(1<<m)-1) rei(i,1,m) if(getbit(x,i)) val[x]+=b[i];
        rei(x,1,(1<<m)-1) rei(i,1,n) if(a[i]==val[x]){
            gt[a[i]].push_back(x);
            break;
        }
        dp[0][0]=1;
        rei(i,0,n-1){
            rei(x,0,(1<<m)-1){
                for(int sub:gt[a[i+1]]){
                    if((sub&x)==0){
                        int y=sub|x;
                        dp[i+1][y]=max(dp[i+1][y],dp[i][x]);
                    }
                }
            }
        }
        int ok=0;
        rei(x,0,(1<<m)-1) if(dp[n][x]) ok=1;
        if(ok) cout<<"YES";
        else cout<<"NO";
    }
}sub4;
/*
dp[i][x] lieu co the toi uu duoc khong 
ta phai dat duoc do phuc tap 2^n * n nghia la chi phi chuyen trang thai cua ta phai trong O(1)

*/
int main(){
    if(fopen(TASK".in","r")){
        freopen(TASK".in","r",stdin);
        freopen(TASK".out","w",stdout);
    }
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    input();
    if(sub1.check()) return sub1.sol(),0;
    if(sub3.check()) return sub3.sol(),0;   
    if(sub4.check()) return sub4.sol(),0;
    // int mask=(1<<5)-1;
    // for(int sub=mask;sub>0;sub=(sub-1)&mask) deb<<sub<<" ";
}
/*
20 20
14 51 201 23 62 14 152 162 189 15 6 45 146 155 178 16 458 186 19 12
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
ta lam sao de duyet cac so mot cach hieu qua va khong lang phi nghia la ta phai chuan bi truoc tap cac doan bang a[i] 
*/

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen(TASK".in","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
bank.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(TASK".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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