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;
typedef long long ll;
int n,m;
vector<int>graph[22];
int A[22],B[22],sum[(1<<20)];
char dp[22][(1<<20)];
char f(int cur,int state){
char&ret = dp[cur][state];
if(~ret) return ret;
ret = 0;
if(cur==n) return ret = 1;
if(A[cur]>sum[(1<<m)-1-state]) return ret;
for(int s : graph[cur]){
if(s&state) continue;
ret|=f(cur+1,state|s);
}
return ret;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
n = 20,m = 20;
for(int i=0; i<n; i++) A[i] = 10;
for(int i=0; i<m; i++) B[i] = 1;
for(int i=1; i<(1<<m); i++){
int tot = 0;
for(int j=0; j<m; j++) if(i&(1<<j)) tot+=B[j];
for(int j=0; j<n; j++) if(A[j]==tot) graph[j].emplace_back(i);
sum[i] = tot;
}
for(int i=n; i>=0; i--) A[i]+=A[i+1];
memset(dp,-1,sizeof(dp));
cout<<(f(0,0)?"YES":"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... |