Submission #868826

#	Time	Username	Problem	Language	Result	Execution time	Memory
868826		vjudge1	Bank (IZhO14_bank)	C++17	0 / 100	1064 ms	20936 KiB

bank

#include<bits/stdc++.h>
using namespace std;
int val[1002], cnt[1002], sal[20], note[20];
map<int,int> c;
int ok[21][1<<20];
vector<int> poss[20];
bool inc(int a, int b) {
    for (int i = 1001; i--;) {
        int x = 0;
        while(a>val[i])
            x++,a-=val[i];
        while(b>val[i])
            x--,b-=val[i];
        if(x<0) return 0;
    }
    return 1;
}
int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        cin >> sal[i];
    for(int i = 0; i < m; i++)
        cin >> note[i], cnt[note[i]]++;
    val[0]=1;
    for(int i = 1; i < 1002; i++)
        val[i]=val[i-1]*(1+cnt[i-1]),c[val[i]]=i;
    ok[0][0]=1;
    for(int i = 0; i < val[1001]; i++) {
        int sum = 0;
        int i2 = i;
        for(int j = 1001; --j;) {
            while(i2>val[j])
                i2-=val[j],sum+=j;
        }
        for(int j = 0; j < m; j++)
            if(sum==sal[j])
                poss[j].push_back(i);
    }
    for(int i = 1; i <= m; i++)
        for(int j = 0; j < val[1001]; j++)
            for(auto k: poss[i-1])
                if(inc(j,k)&&ok[i-1][j-k]) {
                    ok[i][j]=1;
                    if(i==m) {
                        cout << "YES";
                        return 0;
                    }
                    break;
                }
    cout << "NO";   
}

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