제출 #601194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
601194		CSQ31	Uplifting Excursion (BOI22_vault)	C++17	20 / 100	1333 ms	16036 KiB

vault

#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(),a.end()
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long int ll;
ll A[5000],B[5000];
unordered_map<ll,ll>val;
ll dp[2000001];
int main()
{
	int m;
	ll L;
	cin>>m>>L;
	for(int i=-m;i<=m;i++)cin>>A[i+m];
	ll ans = A[m];
	/*
	//subtask 2 m^4 knapsack??
	//consider left and right side separately
	//let ai be number of art piece i chosen
	//1)atleast one of ai , a_{-i} must be 0
	//2)consider only positive
	//ai aj i<j
	//if aj >= i and ai <= Ai-j
	//do ai+=j aj-=i
	//j > i
	//ai <= Ai-M and aj >= M cant be both true
	//a prefix p has ai>Ai-M then p+1 can be anything
	//ahhhhhhhhh iterate first i such that ai <= M
	for(int i=1;i<=m;i++){
	}
	*/
	ll shift = 500500;
	if(L > shift || L < -shift){
		cout<<"impossible"<<'\n';
		return 0;
	}
	for(int i=0;i<=2000000;i++)dp[i] = -1;
	dp[shift] = 0;
	for(ll i=-m;i<=m;i++){
		if(i==0)continue;
		ll z = 1;
		vector<ll>item;
		while(A[i+m]>=z){
			item.push_back(z);
			A[i+m]-=z;
			z*=2;
		}
		if(A[i+m])item.push_back(A[i+m]);
		if(i < 0){
			for(ll x:item){
				for(ll j=-shift-x*i;j<=shift;j++){
					if(dp[j+shift] != -1)dp[j + x*i+shift] = max(dp[j + x*i+shift],dp[j+shift] + x);
				}
			}
		}else{
			for(ll x:item){
				for(ll j=shift-x*i;j>=-shift;j--){
					if(dp[j+shift] != -1)dp[j + x*i+shift] = max(dp[j + x*i+shift],dp[j+shift] + x);
				}
			}			
			
		}
	}
	if(dp[L+shift] == -1){
		cout<<"impossible"<<'\n';
		return 0;
	}
	ans+=dp[L+shift];
	cout<<ans<<'\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