Submission #577873

#	Time	Username	Problem	Language	Result	Execution time	Memory
577873		vanic	Uplifting Excursion (BOI22_vault)	C++14	5 / 100	713 ms	28244 KiB

vault

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <cstring>

using namespace std;

const int maxn=55, maxval=63755;
typedef long long ll;

int a[maxn*2];
int dp[maxval][maxn];

void dodaj1(int br, int x){
	for(int i=x; i<maxval; i++){
		for(int j=1; j<=br; j++){
			if(dp[i-x][j-1]!=-1){
				dp[i][j]=dp[i-x][j-1]+1;
			}
		}
	}
	for(int i=0; i<maxval; i++){
		int maksi=-1;
		for(int j=0; j<=br; j++){
			maksi=max(maksi, dp[i][j]);
			dp[i][j]=-1;
		}
		dp[i][0]=maksi;
	}
}

void dodaj2(int br, int x){
	for(int i=maxval-x-1; i>=0; i--){
		for(int j=1; j<=br; j++){
			if(dp[i+x][j-1]!=-1){
				dp[i][j]=dp[i+x][j-1]+1;
			}
		}
	}
	for(int i=0; i<maxval; i++){
		int maksi=-1;
		for(int j=0; j<=br; j++){
			maksi=max(maksi, dp[i][j]);
			dp[i][j]=-1;
		}
		dp[i][0]=maksi;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(dp, -1, sizeof(dp));
	int n;
	ll l;
	cin >> n >> l;
	assert(n<maxn);
	for(int i=0; i<n*2+1; i++){
		cin >> a[i];
		assert(a[i]<maxn);
	}
	dp[0][0]=a[n];
	if(l<0){
		l=-l;
		for(int i=0; i<n; i++){
			dodaj1(a[i], n-i);
		}
		for(int i=n+1; i<n*2+1; i++){
			dodaj2(a[i], i-n);
		}
	}
	else{
		for(int i=n+1; i<n*2+1; i++){
			dodaj1(a[i], i-n);
		}
		for(int i=0; i<n; i++){
			dodaj2(a[i], n-i);
		}
	}
	if(l>=maxval || dp[l][0]<1){
		cout << "impossible\n";
	}
	else{
		cout <<  dp[l][0] << '\n';
	}
	return 0;
}

• Subtask 1: 5 / 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