Submission #730411

#	Time	Username	Problem	Language	Result	Execution time	Memory
730411		Lalic	Bank (IZhO14_bank)	C++17	0 / 100	2 ms	468 KiB

bank

#include <bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pb push_back
 
typedef long long ll;
typedef pair<int, ll> pii;
typedef pair<ll, ll> pll;

const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;

int main(){
  	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("shuffle.in","r",stdin);
    // freopen("shuffle.out","w",stdout);

	int n, m; cin >> n >> m;

	vector<int> arr(n+1);
	for(int i=1;i<=n;i++) cin >> arr[i];
	vector<int> bank(m);
	for(int i=0;i<m;i++) cin >> bank[i];

	vector<int> ps(n+1); ps[0]=0;
	for(int i=1;i<=n;i++) ps[i]=ps[i-1]+arr[i];

	ps.pb(INF);

	vector<pii> dp((1<<m)); dp[0]={1, 0};
	for(int i=1;i<(1<<m);i++){
		dp[i]={-1, -1};

		for(int j=0;(1<<j)<=i;j++){
			if(!(i&(1<<j))) continue;

			int pos=dp[i-(1<<j)].fi, tot=dp[i-(1<<j)].se+arr[j+1];

			if(tot==ps[pos]) dp[i]={max(dp[i].fi, pos+1), tot};
			else dp[i]={max(dp[i].fi, pos), tot};
		}
	}

	if(dp[(1<<m)-1].fi==n+1) cout << "YES\n";
	else cout << "NO\n";
	return 0;
}

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