Submission #166036

#	Time	Username	Problem	Language	Result	Execution time	Memory
166036		GioChkhaidze	은행 (IZhO14_bank)	C++14	71 / 100	1082 ms	26172 KiB

bank

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int n,m,S0,S1,S2;
int a[22],b[22];

vector < int > D[21];
ll F1[1058576],F2[1058576],F3[1058576];
bool ans[(1<<21)];

main () {
	cin>>n>>m;
	
	for (int i=0; i<n; i++) {
		cin>>a[i];
		S1+=a[i];
	}
	
	for (int i=0; i<m; i++) 
		cin>>b[i];
		
	for (int j=0; j<n; j++) {
		for (int mask=0; mask<(1<<m); ++mask) {
			S0=0;
			for (int i=0; i<m; i++) 
				if ((1<<i)&mask) S0+=b[i];
			if (S0==a[j]) F2[mask]++;
		}
	
	    for (int i=0; i<m; ++i) 
	        for (int mask=0; mask<(1<<m); ++mask)
	            if (mask&(1<<i)) F2[mask]+=F2[mask^(1<<i)];
			
		for (int mask=0; mask<(1<<m); ++mask) {
	        if (!j) F3[mask]=F2[mask];	
			   else F3[mask]=F1[mask]*F2[mask];			 
			F1[mask]=F3[mask];
			F2[mask]=0;
		}
		
		 for (int i=m-1; i>=0; --i) 
	        for (int mask=(1<<m)-1; mask>=0; --mask)
	            if (mask&(1<<i)) F3[mask]-=F3[mask^(1<<i)];
			
		for (int mask=0; mask<(1<<m); ++mask)
			if (!ans[mask] && F3[mask]) ans[mask]=1;
	}
	
	for (int mask=(1<<m)-1; mask>=0; --mask)
		if (ans[mask]) {
			S2=0;
			for (int i=0; i<m; i++)
				if (mask&(1<<i)) S2+=b[i];
				
			if (S1==S2) {
				cout<<"YES\n";
				return 0;
			}
		}
		
	cout<<"NO\n";
}

Compilation message (stderr)

bank.cpp:12:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
bank.cpp: In function 'int main()':
bank.cpp:31:6: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
      for (int i=0; i<m; ++i) 
      ^~~
bank.cpp:35:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int mask=0; mask<(1<<m); ++mask) {
   ^~~

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