oj.uz

Submission #603202

# Submission time Handle Problem Language Result Execution time Memory
603202 2022-07-23T16:59:56 Z MohamedAhmed04 Uplifting Excursion (BOI22_vault) C++14
0 / 100
 5000 ms 16076 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 15956 KB Output is correct
2 Correct 494 ms 15960 KB Output is correct
3 Correct 183 ms 15996 KB Output is correct
4 Correct 1769 ms 15956 KB Output is correct
5 Execution timed out 5023 ms 15964 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 15956 KB Output is correct
2 Correct 494 ms 15960 KB Output is correct
3 Correct 183 ms 15996 KB Output is correct
4 Correct 1769 ms 15956 KB Output is correct
5 Execution timed out 5023 ms 15964 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1773 ms 16076 KB Output is correct
2 Incorrect 4446 ms 15956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1773 ms 16076 KB Output is correct
2 Incorrect 4446 ms 15956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1773 ms 16076 KB Output is correct
2 Incorrect 4446 ms 15956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 15956 KB Output is correct
2 Correct 494 ms 15960 KB Output is correct
3 Correct 183 ms 15996 KB Output is correct
4 Correct 1769 ms 15956 KB Output is correct
5 Execution timed out 5023 ms 15964 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1773 ms 16076 KB Output is correct
2 Incorrect 4446 ms 15956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 15956 KB Output is correct
2 Correct 494 ms 15960 KB Output is correct
3 Correct 183 ms 15996 KB Output is correct
4 Correct 1769 ms 15956 KB Output is correct
5 Execution timed out 5023 ms 15964 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1773 ms 16076 KB Output is correct
2 Incorrect 4446 ms 15956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 15956 KB Output is correct
2 Correct 494 ms 15960 KB Output is correct
3 Correct 183 ms 15996 KB Output is correct
4 Correct 1769 ms 15956 KB Output is correct
5 Execution timed out 5023 ms 15964 KB Time limit exceeded
6 Halted 0 ms 0 KB -