Submission #1289404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289404		aka_brofuck	Bank (IZhO14_bank)	C++20	19 / 100	88 ms	8592 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)];
    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";
    }
}sub3;
struct {
    bool check(){
        return 1;
    }
    int f[(1<<20)],g[(1<<20)];
    void sol(){ 
        rei(x,0,(1<<m)-1){
            int id=f[x]+1;
            if(f[x]==n){
                cout<<"YES";
                return ;
            }
            rei(i,1,m) if(!getbit(x,i)){

                int y=x|(1<<(i-1));
                if(g[x]+b[i]<a[id]){
                    g[y]=g[x]+b[i];
                    f[y]=max(f[x],f[y]);
                }
                if(g[x]+b[i]==a[id]){
                    g[y]=0;
                    f[y]=max(f[x]+1,f[y]);
                }
            }
        }
        int ok=0;
        rei(x,0,(1<<m)-1) if(f[x]==n) 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)
cai nao cung quan trong khong the bo di duoc vay bai toan nay tro thanh bai doi goc nhin 
f[x] so nguoi duoc tra lon nhat neu su dung cac to tien trong nguoi lien tiep dau tien 
g[x] la so tien thua sau khi da tra het so cho f[x] nguoi
them tien x vao xem co the tra cho nguoi i+1 khong --> neu con thua that su cap nhat 
*/
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] 
*/
/*
2 6
9 10
5 4 8 6 3 10
*/

Compilation message (stderr)

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

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