Submission #348875

#	Time	Username	Problem	Language	Result	Execution time	Memory
348875		gmyu	Bank (IZhO14_bank)	C++14	100 / 100	151 ms	8576 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];
/**
 * dp[match] = (this note set has cumulative value of what, it covers up to 1 ... i people
 * if first = 0, it means that it can not exactly match 1 ... i people
 */

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++) {
        int a; cin >> a;
        p[i] += p[i-1] + a;
    }
    for(j=0;j<ctNotes; j++) cin >> n[j];

    dp[0] = mp(0,0);
    for(int match = 1; match < (1<<ctNotes); match++) {
        for(j=0; j<ctNotes; j++) {
            if( (match & (1<<j)) == 0 ) continue;
            int pre = match - (1<<j);
            int prei = dp[pre].snd;
            if ( ( prei==0 && (pre == 0 || dp[pre].fst>0)) || (prei>0 && dp[pre].fst>=p[prei]) ) {
                if(dp[pre].fst + n[j] < p[prei+1]) {
                    dp[match] = mp(dp[pre].fst + n[j], prei);
                } else if(dp[pre].fst + n[j] == p[prei+1]) {
                    dp[match] = mp(dp[pre].fst + n[j], prei+1);
                    if(prei+1 == ctPeople) {
                        cout << "YES" << endl; exit(0);
                    }
                }
            }
        }
    }

    cout << "NO" << endl;

}

Compilation message (stderr)

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

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