제출 #603202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
603202		MohamedAhmed04	Uplifting Excursion (BOI22_vault)	C++14	0 / 100	5023 ms	16076 KiB

vault

#include <bits/stdc++.h>

using namespace std ;

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

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

int dp[2][MAX2] ;

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)
		{
			s.clear() ;
			int cur = 0 ;
			for(int k = 2e6-j ; k >= 0 ; k -= i*-1)
			{
				s.insert(dp[prv][k] - cur) ;
				int a = k + (arr[i+n]+1) * (i*-1) ;
				if(cur > arr[i+n])
					s.erase(s.find(dp[prv][a] - (cur-arr[i+n]-1))) ;
				dp[now][k] = cur + (*s.rbegin()) ;
				++cur ;
			}
		}
	}
	for(int i = 1 ; i <= n ; ++i)
	{
		now = !now , prv = !prv ;
		for(int j = 0 ; j < i ; ++j)
		{
			s.clear() ;
			int cur = 0 ;
			for(int k = j ; k <= 2e6 ; k += i)
			{
				s.insert(dp[prv][k] - cur) ;
				int a = k - (arr[i+n]+1) * i ;
				if(cur > arr[i+n])
					s.erase(s.find(dp[prv][a] - (cur-arr[i+n]-1))) ;
				dp[now][k] = cur + (*s.rbegin()) ;
				++cur ;
			}
		}
	}
	if(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: 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