Submission #644495

#	Time	Username	Problem	Language	Result	Execution time	Memory
644495		amoorj	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	0 / 85	1 ms	468 KiB

necklace

//Yamero codeforces-chan/atcoder-chan/quera-chan
//#pragma GCC optimize ("O3,unroll-loops")
//#pragma GCC target ("avx2,bmi,bmi2,popcnt")
#include <bits/stdc++.h>
#define F first
#define pb push_back
#define sz size()
#define S second
using namespace std;
typedef long long int ll;

const int N = 1000;
int n,m,k,a[N],b[N];
bitset<N*N> dp;


inline void init(){
}
inline void input(){
	cin >> n >> m >> k;
	for(int i=0;i<n;i++)
		cin >> a[i];
	for(int i=0;i<m;i++)
		cin >> b[i];
}
inline void solve(){
	dp[0] = 1;
	for(int i=0;i<m;i++)
		dp |= (dp << b[i]);
	int sum = 0;
	for(int i=0;i<n;i++)
		sum += a[i];
	for(int i=sum;i<N*N;i++){
		if(dp[i]){
			cout << i - sum;
			return;
		}
	}
	cout << "Impossible";
}
int main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	init();
	int queries = 1;
//	cin >> queries;
	while(queries--){
		input();
		solve();
	}
	return 0;
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40