Submission #1046573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046573		vjudge1	Uplifting Excursion (BOI22_vault)	C++17	0 / 100	5093 ms	524288 KiB

vault

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define int long long
#define ld long double

const int N = 1e6 + 20;
const int X = 5e5 + 20;

const int LOG = 21;
const int INF = 1e17;


signed main(){ios::sync_with_stdio(false);cin.tie(0);	
	int n, m;
	cin>>n>>m;
	vector<int> v;
	for(int i = -n;i <= n;i++){
		int x;
		cin>>x;
		for(int j = 0;j < x;j++)v.push_back(i);
	}
	map<int,int> dp;
	dp[0] = 0;
	for(auto u: v){
		map<int, int> ndp = dp;
		for(auto [a, b]: dp){
			ndp[a + u] = max(ndp[a + u], b + 1);
		}
		dp = ndp;
	}
	if(dp.count(m))cout<<dp[m];
	else cout<<"impossible";
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3-1: 0 / 10
• Subtask 3-2: 0 / 10
• Subtask 4-1: 0 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 0 / 10
• Subtask 5-2: 0 / 10
• Subtask 6-1: 0 / 10
• Subtask 6-2: 0 / 10