Submission #348869

#	Time	Username	Problem	Language	Result	Execution time	Memory
348869		gmyu	Bank (IZhO14_bank)	C++14	71 / 100	1093 ms	8812 KiB

bank

/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/IZhO14_bank
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>
#include <set>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define fst first
#define snd second
#define pb  push_back
#define sz(x) (int)(x).size()
#define trav(u, adj_v) for (auto& u: adj_v)

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 100007
#define MAXE 100007

const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
    int x, y;
    int val;
    int visited;
    bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); }
};
struct EDGE {
    int from, to;
    ll weight;
    bool operator<(EDGE other) const { return weight < other.weight; }
};

bool debug;

int ctPeople, ctNotes;
int p[21], n[21];
pii dp[1<<20];


int main() {
    debug = true;
    ios_base::sync_with_stdio(false); cin.tie(0);

    int i, j, k;

    cin >> ctPeople >> ctNotes;
    for(i=1;i<=ctPeople; i++) cin >> p[i];
    for(j=0;j<ctNotes; j++) cin >> n[j];

    int pay = 0;
    for(i=1; i<=ctPeople; i++) {
        //cout << i << endl;
        pay += p[i];
        /// find all match that can pay people i
        dp[0] = mp(0, i);
        for(int match = 1; match < (1<<ctNotes); match++) {
            if( dp[match].snd != i) {
                if( dp[match].fst != pay - p[i]) dp[match].fst = 0;  /// if can not pay 1 ... (i-1) person, then does not work
                dp[match].snd = i;
            }
            for(j=0; j<ctNotes; j++) {
                if( (match & (1<<j)) == 0 ) continue;
                int pre = match - (1<<j);
                if ( ( i==1 && (pre == 0 || dp[pre].fst>0)) || (i>1 && dp[pre].fst>0) ) {
                    if(dp[pre].fst + n[j] <= pay) {
                        dp[match] = mp(dp[pre].fst + n[j], i);
                        //cout << match <<" = " << dp[match].fst << endl;
                    }
                }
            }
        }

    }

    bool canpay = false;
    for(int match = 0; !canpay && match < (1<<ctNotes); match++) {
        if(dp[match].fst == pay && dp[match].snd == ctPeople) canpay = true;
    }

    if(canpay) cout << "YES" << endl;
    else cout << "NO" << endl;

}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:63:15: warning: unused variable 'k' [-Wunused-variable]
   63 |     int i, j, k;
      |               ^

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