Submission #602635

#	Time	Username	Problem	Language	Result	Execution time	Memory
602635		CSQ31	Uplifting Excursion (BOI22_vault)	C++17	100 / 100	817 ms	1748 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];
ll take[5000];
struct item{
	ll w = 0,v = 0,c = 0;
	item(){}
	item(ll a,ll b,ll _c){
		w = a;
		v = b;
		c = _c;
	}
};
int main()
{
	ll m,L;
	cin>>m>>L;
	for(int i=-m;i<=m;i++)cin>>a[i+m];
	//greedy sol and optimal sol distance small
	ll neg = 0,pos = 0;
	for(ll i=-m;i<=0;i++)neg+=i*a[i+m];
	for(ll i=0;i<=m;i++)pos+=i*a[i+m];
	if(L>pos  || L < neg){
		cout<<"impossible";
		return 0;
	}
	if(neg+pos < L){
		for(int i=1;i<=m;i++)swap(a[i+m],a[-i+m]);
		L*=-1;
	}
	ll sum = 0;
	ll cur = a[m];
	vector<item>b;
	for(ll i=-m;i<=-1;i++){
		sum+=a[i+m] * i;
		cur+=a[i+m];
		a[i+m] = min(a[i+m],2*m);
		if(a[i+m])b.push_back(item(i,-1,a[i+m]));
	}
	//weight value count
	for(int i=1;i<=m;i++){
		take[i] = min(a[i+m],(L-sum)/i);
		a[i+m]-=take[i];
		cur+=take[i];
		sum+=i*1LL*take[i]; //add smtg
		if(a[i+m])b.push_back(item(i,1,min(2*m,a[i+m])));
	}
	for(int i=1;i<=m;i++){ //take smtg away
		if(take[i])b.push_back(item(-i,-1,min(2*m,take[i])));
	}
	int mx = 2*m*m;
	const ll INF = 1e18;
	vector<ll>dp(mx+1,-INF);
	dp[0] = 0;
	for(auto x:b){
		int z = 1;
		vector<int>cc;
		while(x.c>=z){
			cc.push_back(z);
			x.c-=z;
			z*=2;
		}
		if(x.c)cc.push_back(x.c);
		if(x.w > 0){
			for(int y : cc){
				for(int i=mx;i >= y * x.w;i--){
					if(dp[i-y * x.w] != -INF)dp[i] = max(dp[i],dp[i - y * x.w] + y * x.v); 
					
				}	
			}
			
		}else{
			for(int y : cc){
				for(int i=0;i <= mx + y * x.w;i++){
					if(dp[i - y * x.w] != -INF)dp[i] = max(dp[i],dp[i - y * x.w] + y * x.v); 
				}	
			}
			
		}
	}
	if(dp[L-sum] != -INF)cout<<cur+dp[L-sum];
	else cout<<"impossible";
}

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