Submission #873950

#	Time	Username	Problem	Language	Result	Execution time	Memory
873950		cocohearts	Bank (IZhO14_bank)	C++11	0 / 100	51 ms	24212 KiB

bank

#include <bits/stdc++.h>
#include <iostream>

using namespace std;

typedef long long        ll;
typedef pair<int, int>   ii;
typedef vector<ii>      vii;
typedef vector<int>      vi;

#define INF 2000000000
#define MOD 1000000007
#define loop(x,n) for(int x = 0; x < n; ++x)
#define iloop(x,a,n) for(int x=a; x<n; ++x)
#define sloop(e,s) for(auto&& e : s)
#define itloop(it,m) for(auto&& it = m.begin(); it!=m.end(); ++it)
#define F first
#define S second
#define PB push_back
#define MP make_pair

// num_paid, left_to_pay; num=-1 if impossible
ii DP[1<<20];

int main() {
    (void)!freopen("bank.in","r",stdin);
    (void)!freopen("bank.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,M;
    cin >> N >> M;
    int salaries[N], notes[M];
    loop(i,N) {
        cin >> salaries[i];
    }
    loop(i,M) {
        cin >> notes[i];
    }
    bool solved = false;
    loop(bm,1<<M) {
        if (solved) break;
        bool works = false;
        if (!bm) {
            DP[bm] = MP(0,salaries[0]);
            continue;
        }
        loop(ind,M) {
            if (bm&1<<ind) {
                int prev = bm^1<<ind;
                if (DP[prev].F<0 || notes[ind]>DP[prev].S) continue;

                if (notes[ind]<=DP[prev].S) {
                    DP[bm] = DP[prev];
                    DP[bm].S -= notes[ind];
                } else if (DP[prev].S==0) {
                    if (salaries[DP[prev].F+1]>=notes[ind]) {
                        DP[bm] = MP(DP[prev].F+1,salaries[DP[prev].F+1]-notes[ind]);
                    } else {continue;}
                }
                works = true;
            }
        }
        if (DP[bm] == MP(N-1,0)) {
            solved = true;
            cout << "YES";
        }
        if (!works) {
            DP[bm] = MP(-1,0);
        }
        // cerr << bm << ": " << DP[bm].F << " " << DP[bm].S << "\n";
    }
    if (!solved) cout << "NO";
}

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