Submission #392464

#	Time	Username	Problem	Language	Result	Execution time	Memory
392464		patrikpavic2	Bank (IZhO14_bank)	C++17	100 / 100	115 ms	14764 KiB

bank

#include <cstdio>
#include <vector>
#include <cstring>

#define PB push_back

using namespace std;

const int N = 20;
const int MSK = (1 << 20);

vector < int > v[N];
int A[N], B[N], n, m, P[N];
int dp[MSK], sm[MSK];

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 0;i < n;i++){
		scanf("%d", A + i);
		P[i] = A[i] + (i ? P[i - 1] : 0);
	}
	for(int i = 0;i < m;i++)
		scanf("%d", B + i);
	for(int msk = 0;msk < (1 << m);msk++){
		for(int i = 0;i < m;i++)
			sm[msk] += B[i] * !!(msk & (1 << i));
		int gd = 0;
		while(gd < n && P[gd] < sm[msk]) gd++;
		v[gd].PB(msk); dp[msk] = 1;
	}
	for(int i = 1;i <= n;i++){
		vector < int > dobri;
		for(int x : v[i - 1]) 
			if(sm[x] == P[i - 1] && dp[x])
				dobri.PB(x);
		memset(dp, 0, sizeof(dp));
		if(i == n){
			printf((int)dobri.size() ? "YES\n" : "NO\n");
			return 0;
		}
		memset(dp, 0, sizeof(dp));
		for(int x : dobri) dp[x] = 1;
		for(int j = 0;j < m;j++){
			for(int x : v[i]){
				if(x & (1 << j))
					dp[x] |= dp[x ^ (1 << j)];
			}
		}
	}
	return 0;
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
bank.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |   scanf("%d", A + i);
      |   ~~~~~^~~~~~~~~~~~~
bank.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |   scanf("%d", B + i);
      |   ~~~~~^~~~~~~~~~~~~

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