Submission #166046

#	Time	Username	Problem	Language	Result	Execution time	Memory
166046		GioChkhaidze	Bank (IZhO14_bank)	C++14	100 / 100	895 ms	13944 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],f1[1002],f2[1002];
int F1[1058576],F3[1058576],F2[1058576];
bool ans[1058576];
main () {
	cin>>n>>m;
	
	for (i=0; i<n; i++) {
		cin>>a[i];
		f1[a[i]]++;
	}
	
	for (i=0; i<m; i++) {
		cin>>b[i];
		f2[b[i]]++;
	}
	
	n=0,m=0;
	for (i=1; i<=1000; i++) 
		if (f1[i]>f2[i]) {
			for (j=f2[i]+1; j<=f1[i]; j++)
				a[n++]=i,S1+=i;
		}
			else {
			for (j=f1[i]+1; j<=f2[i]; j++)
				b[m++]=i;	
		}
	
	if (!n) {
		cout<<"YES\n";
		return 0;
	}
		
	int M=(1<<m);	
		
	for (j=0; j<n; j++) {
		for (mask=0; mask<M; ++mask) {
			S0=0;
			for (i=0; i<m; i++) 
				if ((mask>>i)&1) {
					S0+=b[i];
					if (S0>a[j]) break;
				}
					
			if (S0==a[j]) F2[mask]=1;
		}
	
	    for (i=0; i<m; ++i) 
	        for (mask=0; mask<M; ++mask)
	            if (mask & (1<<i)) 
					F2[mask]+=F2[mask^(1<<i)];
			
		for (mask=0; mask<M; ++mask) {
	        if (!j) F3[mask]=F2[mask];	
			   else F3[mask]=F1[mask]*F2[mask];			 
			F1[mask]=F3[mask];
		}
		
		 for (i=m-1; i>=0; --i) 
	        for (mask=(1<<m)-1; mask>=0; --mask)
	            if (mask & (1<<i)) 
					F3[mask]-=F3[mask^(1<<i)];
			
		for (mask=0; mask<M; ++mask)
			ans[mask]|=F3[mask],F2[mask]=0;
	}
	
	for (mask=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:10:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
bank.cpp: In function 'int main()':
bank.cpp:53:6: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
      for (i=0; i<m; ++i) 
      ^~~
bank.cpp:58:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (mask=0; mask<M; ++mask) {
   ^~~

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