Submission #1077413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077413		wangziyanmo	Uplifting Excursion (BOI22_vault)	C++14	20 / 100	1569 ms	8384 KiB

vault

#include <bits/stdc++.h>
using namespace std;

#define int long long

int dp[3000010];
int a[10000],w[10000];
int siz;

signed main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,q;cin>>n>>q;
	for (int i=-n;i<=n;i++){
		int k;cin>>k;
		int num=1;
		while (k>=num){
			k-=num;
			a[++siz]=num*i;
			w[siz]=num;
			num<<=1;
		}
		if (k>0){
			a[++siz]=k*i;
			w[siz]=k;
		}
	}
	//for (int i=1;i<=siz;i++) cout<<a[i]<<' '<<w[i]<<"\n";
	for (int i=0;i<=1010000;i++) dp[i]=-1e18;
	dp[505000]=0;
	for (int i=1;i<=siz;i++){
		if (a[i]<0){
			for (int j=0;j<=1010000;j++){
				if (j-a[i]>=0 && j-a[i]<=1010000 && dp[j-a[i]]!=-1e18){
					dp[j]=max(dp[j],dp[j-a[i]]+w[i]);
				}
			}
			continue;
		}
		for (int j=1010000;j>=0;j--){
			if (j-a[i]>=0 && j-a[i]<=1010000 && dp[j-a[i]]!=-1e18){
				dp[j]=max(dp[j],dp[j-a[i]]+w[i]);
			}
		}
	}
	if (q>505000 || q<-505000 || dp[505000+q]==-1e18) cout<<"impossible\n";
	else cout<<dp[505000+q]<<"\n";
}

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