Submission #1136311

#TimeUsernameProblemLanguageResultExecution timeMemory
1136311abel2008Bank (IZhO14_bank)C++17
100 / 100
93 ms8624 KiB
#include <iostream>
#include <fstream>
#include <utility>
using namespace std;
ifstream fin("bank.in");
ofstream fout("bank.out");
int salary[25],notes[25],n,m;
pair<int,int> dp[1<<20];
// {completed salaries,currsum}

pair<int,int> calc(pair<int,int> pi,int note) {
        int crtsalary = pi.first+1;
        int crtsum = pi.second;
        if (crtsum+note==salary[crtsalary]) {
                return {pi.first+1,0};
        } else if (crtsum+note<salary[crtsalary]) {
                return {pi.first,pi.second+note};
        } else {
//                return {pi.first,pi.second+note};
                return {-1,-1};
        }
}

int main() {
        cin>>n>>m;
        for (int i = 1;i<=n;++i)
                cin>>salary[i];
        for (int i = 1;i<=m;++i)
                cin>>notes[i];
        for (int i = 0;i<(1<<m);++i) {
                dp[i] = {-1,-1};
        }
        dp[0] = {0,0};
        for (int mask = 1;mask<(1<<m);++mask) {
                for (int j = 0;j<m;++j) {
                        if (mask&(1<<j)
//                        &&dp[mask-(1<<j)].first!=-1
                        ) {
                                dp[mask] = max(calc(dp[mask-(1<<j)],notes[j+1]),dp[mask]);
                        }
                }
                if (dp[mask].first==n) {
                        cout<<"YES";
                        return 0;
                }
        }
        cout<<"NO";
        return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...