Submission #1136311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136311		abel2008	Bank (IZhO14_bank)	C++17	100 / 100	93 ms	8624 KiB

bank

#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;
}

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