Submission #166037

#	Time	Username	Problem	Language	Result	Execution time	Memory
166037		GioChkhaidze	Bank (IZhO14_bank)	C++14	71 / 100	1065 ms	26104 KiB

bank

#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,S0,S1,S2,i,j,mask;
int a[22],b[22];
ll F1[1058576],F2[1058576],F3[1058576];
bool ans[(1<<21)];

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

Compilation message (stderr)

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

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