Submission #439440

#	Time	Username	Problem	Language	Result	Execution time	Memory
439440		2548631	Bank (IZhO14_bank)	C++17	100 / 100	156 ms	16844 KiB

bank

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> cp;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vii;
typedef vector<cp> vcp;
typedef vector<ld> vld;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vii> vvii;

#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define forw(i,l,r) for( int i = (l) ; i < (r) ; i++ )
#define forb(i,r,l) for( int i = (r) ; i >= (l) ; i-- )
#define log2i(x) (64 - __builtin_clzll(1ll*(x)) - 1)
#define numBit(x) (__builtin_popcountll(1ll*(x)))
#define getBit(x,i) ((x)>>(i)&1)
#define Pi acos(-1.0l)
#define sz(x) int(x.size())
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define debug(x) cerr << #x << " = " << x << '\n';

const int N = 21;
const int inf = 1e9;
int n,m;
int a[N],b[N],ma_pp[1<<N],lft[1<<N];

int main() {
    fastIO;
#ifndef ONLINE_JUDGE
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
#endif // ONLINE_JUDGE

    cin >> n >> m;
    forw(i,0,n) cin >> a[i];
    forw(i,0,m) cin >> b[i];
    memset(ma_pp,-1,sizeof ma_pp);
    memset(lft,-1,sizeof lft);
    ma_pp[0]=0; lft[0]=0;
    a[n]=inf;
    forw(i,0,1<<m) {
        forw(j,0,m) if(getBit(i,j)) {
            int mask=i-(1<<j), rem=lft[mask]+b[j];
            if(ma_pp[mask]==-1) continue;
            pii tmp={-1,0};
            if(rem<a[ma_pp[mask]]) {
                tmp.fi=ma_pp[mask];
                tmp.se=rem;
            } else if(rem==a[ma_pp[mask]]) {
                tmp.fi=ma_pp[mask]+1;
                tmp.se=0;
            }
            if(tmp.fi>ma_pp[i]) {
                ma_pp[i]=tmp.fi;
                lft[i]=tmp.se;
            }
        }
    }
    if(ma_pp[(1<<m)-1]==n) cout << "YES\n";
    else cout << "NO\n";
    return 0;
}

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