Submission #1046577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046577		vjudge1	Uplifting Excursion (BOI22_vault)	C++17	0 / 100	5050 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 = 5e6 + 20;
const int X = 7e5 + 20;

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

int dp[2][N];

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);
	}
	memset(dp, -1,sizeof dp);
	dp[0][X] = 0;
	int k = 0;
	for(auto u: v){
		memcpy(dp[k ^ 1], dp[k], sizeof dp[k]);
		for(int i = 0;i < N;i++){
			if(dp[k][i] == -1)continue;
			dp[k ^ 1][i + u] = max(dp[k ^ 1][i + u], dp[k][i] + 1);
		}
		k ^= 1;
	}
	if(dp[k][X + m] != -1)cout<<dp[k][X + 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