Submission #603217

#	Time	Username	Problem	Language	Result	Execution time	Memory
603217		MohamedAhmed04	Uplifting Excursion (BOI22_vault)	C++14	20 / 100	4512 ms	18672 KiB

vault

#include <bits/stdc++.h>

using namespace std ;

struct Max_queue
{

deque< pair<int , int> >q ;
public:
	void insert(int val , int idx)
	{
		while(!q.empty() && val >= q.back().first)
			q.pop_back() ;
		q.emplace_back(val , idx) ;
	}

	void erase(int idx)
	{
		if(q.front().second == idx)
			q.pop_front() ;
	}

	int Max()
	{
		return (q.front().first) ;
	}

	void clear()
	{
		q.clear() ;
	}
};

const int MAX = 100 + 10 ;
const int ZERO = 1e6 ;
const int MAX2 = 2e6 + 10 ;

int arr[2*MAX] ;
int n ;
long long l ;

int dp[2][MAX2] ;

Max_queue q ;

multiset<int>s ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>l ;
	for(int i = -n ; i <= n ; ++i)
		cin>>arr[i+n] ;
	for(int i = 0 ; i <= 2e6 ; ++i)
		dp[0][i] = -1e9 ;
	dp[0][ZERO] = 0 ;
	int now = 0 , prv = 1 ;
	for(int i = -n ; i < 0 ; ++i)
	{
		now = !now , prv = !prv ;
		for(int j = 0 ; j < i*-1 ; ++j)
		{
			q.clear() ;
			int cur = 0 ;
			for(int k = 2e6-j ; k >= 0 ; k -= i*-1)
			{
				q.insert(dp[prv][k] - cur , k) ;
				int a = k + (arr[i+n]+1) * (i*-1) ;
				if(cur > arr[i+n])
					q.erase(a) ;
				dp[now][k] = cur + q.Max() ;
				++cur ;
			}
		}
	}
	for(int i = 1 ; i <= n ; ++i)
	{
		now = !now , prv = !prv ;
		for(int j = 0 ; j < i ; ++j)
		{
			q.clear() ;
			int cur = 0 ;
			for(int k = j ; k <= 2e6 ; k += i)
			{
				q.insert(dp[prv][k] - cur , k) ;
				int a = k - (arr[i+n]+1) * i ;
				if(cur > arr[i+n])
					q.erase(a) ;
				dp[now][k] = cur + q.Max() ;
				++cur ;
			}
		}
	}
	if(abs(l) <= 1e6 && dp[now][ZERO+l] + arr[n] >= 0)
		cout<<dp[now][ZERO+l] + arr[n]<<"\n" ;
	else
		cout<<"impossible\n" ;
	return 0 ;
}

• 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