Submission #467759

#	Time	Username	Problem	Language	Result	Execution time	Memory
467759		quocnghia32	Bank (IZhO14_bank)	C++14	71 / 100	1081 ms	23088 KiB

bank

#include <bits/stdc++.h>
#define TASK "Bank"
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define READFILE freopen(TASK".INP","r",stdin)
#define WRITEFILE freopen(TASK".OUT","w",stdout)
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define ENDL '\n'
#define debug(x) cout<<#x<<" = "<<x<<ENDL
#define fi first
#define se second
#define ever (;true;)
#define all(x) x.begin(),x.end()
#define sz(a) ((int)(a).size())
#define ms(a,x) memset(a,x,sizeof(a))
#define int long long

using namespace std;
typedef vector <int> vi;
typedef pair <int,int> ii;
typedef vector <ii> vpi;
typedef pair <int,ii> iii;
const int N = 30;
const int oo=0x3f;
const int mod=1e9+7;
const int dx[]={-1,0,1,0};
const int dy[]={0,-1,0,1};
int a[N], cost[N];
void init(){
  FAST;

}
signed main()
{
  init();
    int n,m;
    cin >> n >> m;
    For(i,1,n) cin >> a[i];
    For(i,1,m) cin >> cost[i];
    int mm=1<<m;
    vector<ii> p;
    for (int mask=1; mask<mm; mask++){
        int res=0;
        For(j,0,m-1) if ((mask>>j)&1) res+=cost[j+1];
        p.pb({mask,res});
    }
    vector<int> b[n+2];
    vector<int> ans[n+2];
    For(i,1,n){
        for (int j=0; j<p.size(); j++){
            if (p[j].se==a[i]) b[i].pb(p[j].fi);
        }
    }
    p.clear();
    For(i,1,n){
        p.pb({b[i].size(),i});
    }
    sort(all(p));
    if (p[0].fi==0) {
        cout << "NO";
        return 0;
    }

    for (int i=0; i<p.size(); i++){
        int u=p[i].se;
        if (i==0){
            for (int v:b[u]) ans[i].pb(v);
            continue;
        }
        for (int s:ans[i-1])
            for (int v:b[u])
                if ((s&v)==0) ans[i].pb(s|v);
    }
    if (ans[n-1].size()) {
        cout << "YES";
    }else cout << "NO";
  return 0;
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:51:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int j=0; j<p.size(); j++){
      |                       ~^~~~~~~~~
bank.cpp:65:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i=0; i<p.size(); i++){
      |                   ~^~~~~~~~~

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