Submission #1056475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056475		YourEternalReward	Bank (IZhO14_bank)	C++14	100 / 100	101 ms	17032 KiB

bank

/*

               .;;;;:
              :::::::;
              ;::::::;
               :;;;;.
                 ;:::;
                 ;:::::;;                                                           ;;;
                ::::::::::;;                                                       ;:::
                ;:::::::::::;;:                                                  .;;:::
               .;::::::::::::::;;.                  .:.::::                   ;;;:::;;;
               :;:::::::::::::::::;;.            :. .::::....:            :;;::::::::;
               ;::::::::::....:::::::;;;;;;;;;;: .:...  ....:..:      .;;::::::::::::;
              :;::::::::........::::::::::::::. :. .. ...  .  .....;;;:::::::::::::::;
              ;::::::::..........::::::::::::: ....   .....   .....:::::::::::::::::;:
             .;:::::::...........::::::::::::  :.. ...    ...........:::::::::::::::;.
            ......................::::::::::: ..   ....    ..............:::::::::::;
            ..........:::.......:::::::::::::. . ..    ....    ............:::::::::;
            ..........::::::::::::::::.......: .:....    ...    ........ .:  ::::::;;
              ........:::::::::::::...........:. ::. ....   ....    ....   .: .::::;:
              .......:::::::::::::..............::. .::..     ..    ....    .:..:::;:
               ...::::::::::::::::..:::....::....::::.   :....   ....   ....  : ::.
               ;::::::::::::::::::..::.....:::...::::::::. .:.    ...   ..... .. .
              :;::::::::;;   .;:::::............:::::::::::  :....    ... ..  :.:
              ;:::::::;.        ;;:::.......:::::;;;;..;;;::. :....   ....   ...:
              ;:::::;:            .;;::::::;;;;.           ;;:...   ..  .. .:. .
              ;::::::                :;;:                   .;:: ....... .:. :
              ;::::;     ;.                                   ;;::  :::.. .:;:
              ;;::;:    :;;;;;;                               .;::::::::::::;
               ;::;:    .;;;;;;;                               :;::::::::::::
               .;:;:    .::;;;;;                               .;::::::::::;.
                .;;;.....;;;;;;       ...                      .;:::::::::;.
                  ;;:....             .:.          ;;;;;;      :;::::::::;.
                   :;:.........                        .....   ;:::::::;:
                    .............       ..             ...... :;:::::;:
                ................... .;;;.  .:;.              ;;:::;;:
               ..  .......        ..:;;:;;      ;:         :;::;;:
               ;.:::..   ..........:;;;;;        .;...:.;;;;;.               .
               :;:;.................;.;:;         ;:::::::::             ;;;:::
                  .;....:........;; ;;:::;        .:::::;;:::;.:::.   .;:::::::
                  .:...:; ;..:.:.:::.:;;;:::.       :;:: :   ..:.:.     .;:::::
                  ::.........;;+:....:; .:..::        .::..;           ;::;:;;:
                  ;:...........::;;;;;:  .:: .;      ::..:. :.       ;:::;.  :.
                  ::::::...;.        ::::      ..;;;.        ;.   ;;:::;.
                  .. ::.;:.;:     .::;;;                      ;;;:::;;.
                ::.;   :;;;;:::........;                      ;:::;:
               .;...::::........;:.....:;                     ;:
*/

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define endl '\n'
#define rep(i,a,b) for(int i=a; i<=b; ++i)
#define rev(i,b,a) for(int i=b; i>=a; --i)
#define pii pair<ll,ll>
#define getbit(x,i) (x & (1ll<<i))
#define isz(v) (int)(v).size()
#define ALL(v) (v).begin(), (v).end()
using namespace std;
const int maxN = 1e5 + 7;
const ll inf = 1e9 + 7;
const ll mod = (1ll<<31) - 1;
const ll moreinf = 1e16 + 7;
const int AT = 2000;
const int BASE = 31;
const ld pi = acos(-1);
const ld eps = 1e-9;

int n,m;
ll p[21],b[21];
pii f[1<<21];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
    cin >> n >> m;
    rep(i,1,n) cin >> p[i];
    rep(i,1,m) cin >> b[i];
    rep(i,1,(1<<n)-1) f[i] = {-1,-1};
    f[0] = {0,0};
    rep(mask,0,(1<<m)-1){
        rep(i,0,m-1){
            if(getbit(mask,i) || f[mask].first == -1) continue;
            int submask = mask ^ (1<<i);
            pii t = f[mask];
            t.second += b[i+1];
            if(t.second == p[t.first+1]){
                t.first++;
                t.second = 0;
            }
            f[submask] = max(f[submask],t);
        }
        if(f[mask].first==n){
            cout << "YES";
            return 0;
        }
    }
    cout << "NO";
    return 0;   
}

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