Submission #602550

#	Time	Username	Problem	Language	Result	Execution time	Memory
602550		CSQ31	Uplifting Excursion (BOI22_vault)	C++17	0 / 100	1 ms	212 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];
vector<ll>knapsack(int n,vector<int>item){
	vector<ll>dp(n+1,-1e18);
	dp[0] = 0;
	int m = item.size()-1;
	for(int i=1;i<=m;i++){
		int x = item[i];
		int z = 1;
		while(x>=z){
			x-=z;
			for(int j=n;j>=i*z;j--)dp[j] = max(dp[j],dp[j-i*z] + z);
			z*=2;
		}
		if(x)for(int j=n;j>=i*x;j--)dp[j] = max(dp[j],dp[j-i*x] + x);
	}
	return dp;
	
}
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(!(neg<=L && L<=pos)){
		cout<<"impossible";
		return 0;
	}
	if(neg+pos<L){
		cout<<"impossible"<<'\n';
		return 0;
	}//cout<<neg<<" "<<pos<<" "<<L<<'\n';
	ll cur = 0;
	vector<int>item(m+1);
	for(int i=-m;i<0;i++)item[-i] = min(2*m,A[i+m]);
	for(ll i=1;i<=m;i++){
		if(neg+i > L)break;
		ll take = min((L-neg)/i ,A[i+m]);
		A[i+m]-=take;
		neg+=take*i;
		cur+=take;
	}
    vector<ll>dp1 = knapsack(2*m,item);
    for(int i=1;i<=m;i++)item[i] = min(2*m,A[i+m]);
	vector<ll>dp2 = knapsack(2*m,item);
	int need = L-neg;
	ll ans = -1e18;
	for(int i=need;i<=2*m;i++){
		if(dp2[i] >=0 && dp1[i-need]>=0)ans = max(ans,dp2[i] + dp1[i-need]);
	}
	if(ans==-1e18)cout<<"impossible"<<'\n';
	else cout<<ans + A[m] + cur<<'\n';
		
}

• 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