Submission #601177

#	Time	Username	Problem	Language	Result	Execution time	Memory
601177		CSQ31	Uplifting Excursion (BOI22_vault)	C++17	0 / 100	1319 ms	524288 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,dp;
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++){
	}
	*/
	dp[0] = 0;
	for(ll i=1;i<=m;i++){
		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]);
		for(ll x:item){
			vector<array<ll,2>>upd;
			for(auto y:dp)upd.push_back({x*i+y.first,y.second+x});
			for(auto x:upd)dp[x[0]] = max(dp[x[0]],x[1]);
		}
	}
	if(dp.find(L) == dp.end())cout<<"impossible";
	else cout<<dp[L]+A[m]<<'\n';
	
	
}

Compilation message (stderr)

vault.cpp: In function 'int main()':
vault.cpp:14:5: warning: unused variable 'ans' [-Wunused-variable]
   14 |  ll ans = A[m];
      |     ^~~

• 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