This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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";
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |