Submission #1275502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275502		sudama_bera	Bank (IZhO14_bank)	C++20	100 / 100	94 ms	8652 KiB

bank

#include <bits/stdc++.h>
using namespace std;
const long long  M = 1e9+7;
//unbounded knapsack then loop from 0->k
// 0/1 knapsack i.e only use once then loop k->0
template<typename T>
using min_pq=priority_queue<T,vector<T>,greater<T>>;


//(n)C(k)=(n-1)C(k-1)+(n-1)C(k) base case if nCn==0Cn==1

// product of all divisors 
// int cnt =1  pro=(exp(pro,e+1)*(exp(exp(num,(e*(e+1))/2),cnt)))%M;
// cnt=cnt*(e+1)%(M-1);
long long inv(long long x) {
    return x <=1?x:(long long)(M-M/x)*inv(M%x)%M;
    // M=k*a+r
    
}
long long f(long long num,long long denom){
   return ((num%M)*inv(denom))%M;
}
long long exp(long long a,long long b){
    long long ans=1;
    a=a%M;
    while(b){
        if(b&1){
            ans=(ans*a)%M;
        }
        a=(a*a)%M;
        b=b>>1;
    }
    return ans%M;
}
const int MX=1e6+3;
long long  FACT[MX];
long long INV_FACT[MX];
void fact(){
    FACT[0]=1;
    for(int i=1;i<=MX;i++){
        FACT[i]=(FACT[i-1]*i)%M;
    }
}
void fact_inv(){
    /*
       inv(n!)=(n+1)*inv(n+1)*(inv(n!))
       inv(n!)=(n+1)*(inv((n+1)!))


    */ 
    INV_FACT[MX]=exp(FACT[MX],M-2);
    for(int i=MX-1;i>=0;i--){
      INV_FACT[i]=(INV_FACT[i+1]*(i+1))%M;
    }
}
// de_arangement int c=1;
// c=c*i+(i%2==0?1:-1);
// n!{sum((-1)^k)/k!}  k from 0 to n

// stars and bars *|**|** (N+K-1)CN
// x1+x2....xk=n then number of solutions xi>=0 is above

long long D[6];
void d(){
    D[0]=1;
    for(int i=1;i<=6;i++){
        D[i]=D[i-1]*i+(i%2==0?1:-1);
    }
}
// nCk=n-1Ck+n-1Ck-1
long long NCX[1001][1001];
void cal_ncx(){
    NCX[0][0]=1;
    for(int i=1;i<=1000;i++){
        NCX[i][0]=1;
    }
    NCX[1][1]=1;
    for(int i=2;i<=1000;i++){
        for(int j=1;j<=i;j++){
            NCX[i][j]=NCX[i-1][j]+NCX[i-1][j-1];
        }
    }
}
//power of p in n! 
int ff(int n,int p){
    int x=0;
    while(n){
        x+=(n/p);
        n=n/p;
    }
    return x;
}

#define f first
#define s second
using ll=long long;
using ld=long double;
const long long inf=1e18;
void solve(){
   int n,m;cin>>n>>m;
   vector<int>a(n),b(m);
   for(int i=0;i<n;i++){
    cin>>a[i];
   }
   for(int i=0;i<m;i++){
    cin>>b[i];
   }
   //people_paid[s] maximum number of people paid using a subset of the notes
   //left_over[s] it's the money that is extra left after paying those people using subset s of notes
   vector<int>people_paid((1<<m),-1);
   vector<int>leftover((1<<m),-1);
   people_paid[0]=0;
   leftover[0]=0;
   for(int i=0;i<(1<<m);i++){
      for(int j=0;j<m;j++){
        if(i&(1<<j)){
            auto prev=i&(~(1<<j));
            if(people_paid[prev]!=-1){
                int already_paid=people_paid[prev];
                int new_amt=leftover[prev]+b[j];
                int target=a[already_paid];
                if(new_amt<target){
                    people_paid[i]=people_paid[prev];
                    leftover[i]=new_amt;
                }else if(new_amt==target){
                    people_paid[i]=people_paid[prev]+1;
                    leftover[i]=0;
                }
            }
        }
      }
      if(people_paid[i]==(n)){
        cout<<"YES"<<endl;
        return;
      }
   }
   cout<<"NO"<<endl;
}
int main(){
    //freopen("movie.in","r",stdin);
    //freopen("movie.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
  //  cin>>t;
//     fact();
 //   fact_inv();

    while(t--){
    solve();
    }
}

Compilation message (stderr)

bank.cpp: In function 'void fact()':
bank.cpp:41:16: warning: iteration 1000002 invokes undefined behavior [-Waggressive-loop-optimizations]
   41 |         FACT[i]=(FACT[i-1]*i)%M;
      |         ~~~~~~~^~~~~~~~~~~~~~~~
bank.cpp:40:18: note: within this loop
   40 |     for(int i=1;i<=MX;i++){
      |                 ~^~~~
bank.cpp: In function 'void d()':
bank.cpp:67:13: warning: iteration 5 invokes undefined behavior [-Waggressive-loop-optimizations]
   67 |         D[i]=D[i-1]*i+(i%2==0?1:-1);
      |         ~~~~^~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:66:18: note: within this loop
   66 |     for(int i=1;i<=6;i++){
      |                 ~^~~

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