oj.uz

Submission #603217

# Submission time Handle Problem Language Result Execution time Memory
603217 2022-07-23T17:13:32 Z MohamedAhmed04 Uplifting Excursion (BOI22_vault) C++14
20 / 100
 4512 ms 18672 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 15956 KB Output is correct
2 Correct 69 ms 15956 KB Output is correct
3 Correct 28 ms 15888 KB Output is correct
4 Correct 241 ms 15956 KB Output is correct
5 Correct 2451 ms 15964 KB Output is correct
6 Correct 2767 ms 15956 KB Output is correct
7 Correct 2426 ms 15956 KB Output is correct
8 Correct 2455 ms 15956 KB Output is correct
9 Correct 2310 ms 15956 KB Output is correct
10 Correct 2214 ms 15964 KB Output is correct
11 Correct 2292 ms 15960 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 15956 KB Output is correct
2 Correct 69 ms 15956 KB Output is correct
3 Correct 28 ms 15888 KB Output is correct
4 Correct 241 ms 15956 KB Output is correct
5 Correct 2451 ms 15964 KB Output is correct
6 Correct 2767 ms 15956 KB Output is correct
7 Correct 2426 ms 15956 KB Output is correct
8 Correct 2455 ms 15956 KB Output is correct
9 Correct 2310 ms 15956 KB Output is correct
10 Correct 2214 ms 15964 KB Output is correct
11 Correct 2292 ms 15960 KB Output is correct
12 Correct 46 ms 15868 KB Output is correct
13 Correct 74 ms 15936 KB Output is correct
14 Correct 27 ms 15948 KB Output is correct
15 Correct 238 ms 15956 KB Output is correct
16 Correct 2409 ms 15956 KB Output is correct
17 Correct 2405 ms 15956 KB Output is correct
18 Correct 2427 ms 15956 KB Output is correct
19 Correct 2396 ms 15960 KB Output is correct
20 Correct 2374 ms 15960 KB Output is correct
21 Correct 2404 ms 15956 KB Output is correct
22 Correct 2501 ms 15956 KB Output is correct
23 Correct 4512 ms 15960 KB Output is correct
24 Correct 4202 ms 15956 KB Output is correct
25 Correct 4380 ms 15956 KB Output is correct
26 Correct 4153 ms 15956 KB Output is correct
27 Correct 4340 ms 15960 KB Output is correct
28 Correct 4217 ms 15960 KB Output is correct
29 Correct 4160 ms 15964 KB Output is correct

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 15956 KB Output is correct
2 Incorrect 1247 ms 18672 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 252 ms 15956 KB Output is correct
2 Incorrect 1247 ms 18672 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 252 ms 15956 KB Output is correct
2 Incorrect 1247 ms 18672 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 47 ms 15956 KB Output is correct
2 Correct 69 ms 15956 KB Output is correct
3 Correct 28 ms 15888 KB Output is correct
4 Correct 241 ms 15956 KB Output is correct
5 Correct 2451 ms 15964 KB Output is correct
6 Correct 2767 ms 15956 KB Output is correct
7 Correct 2426 ms 15956 KB Output is correct
8 Correct 2455 ms 15956 KB Output is correct
9 Correct 2310 ms 15956 KB Output is correct
10 Correct 2214 ms 15964 KB Output is correct
11 Correct 2292 ms 15960 KB Output is correct
12 Correct 252 ms 15956 KB Output is correct
13 Incorrect 1247 ms 18672 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 15956 KB Output is correct
2 Incorrect 1247 ms 18672 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 47 ms 15956 KB Output is correct
2 Correct 69 ms 15956 KB Output is correct
3 Correct 28 ms 15888 KB Output is correct
4 Correct 241 ms 15956 KB Output is correct
5 Correct 2451 ms 15964 KB Output is correct
6 Correct 2767 ms 15956 KB Output is correct
7 Correct 2426 ms 15956 KB Output is correct
8 Correct 2455 ms 15956 KB Output is correct
9 Correct 2310 ms 15956 KB Output is correct
10 Correct 2214 ms 15964 KB Output is correct
11 Correct 2292 ms 15960 KB Output is correct
12 Correct 46 ms 15868 KB Output is correct
13 Correct 74 ms 15936 KB Output is correct
14 Correct 27 ms 15948 KB Output is correct
15 Correct 238 ms 15956 KB Output is correct
16 Correct 2409 ms 15956 KB Output is correct
17 Correct 2405 ms 15956 KB Output is correct
18 Correct 2427 ms 15956 KB Output is correct
19 Correct 2396 ms 15960 KB Output is correct
20 Correct 2374 ms 15960 KB Output is correct
21 Correct 2404 ms 15956 KB Output is correct
22 Correct 2501 ms 15956 KB Output is correct
23 Correct 4512 ms 15960 KB Output is correct
24 Correct 4202 ms 15956 KB Output is correct
25 Correct 4380 ms 15956 KB Output is correct
26 Correct 4153 ms 15956 KB Output is correct
27 Correct 4340 ms 15960 KB Output is correct
28 Correct 4217 ms 15960 KB Output is correct
29 Correct 4160 ms 15964 KB Output is correct
30 Correct 252 ms 15956 KB Output is correct
31 Incorrect 1247 ms 18672 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 15956 KB Output is correct
2 Incorrect 1247 ms 18672 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 47 ms 15956 KB Output is correct
2 Correct 69 ms 15956 KB Output is correct
3 Correct 28 ms 15888 KB Output is correct
4 Correct 241 ms 15956 KB Output is correct
5 Correct 2451 ms 15964 KB Output is correct
6 Correct 2767 ms 15956 KB Output is correct
7 Correct 2426 ms 15956 KB Output is correct
8 Correct 2455 ms 15956 KB Output is correct
9 Correct 2310 ms 15956 KB Output is correct
10 Correct 2214 ms 15964 KB Output is correct
11 Correct 2292 ms 15960 KB Output is correct
12 Correct 46 ms 15868 KB Output is correct
13 Correct 74 ms 15936 KB Output is correct
14 Correct 27 ms 15948 KB Output is correct
15 Correct 238 ms 15956 KB Output is correct
16 Correct 2409 ms 15956 KB Output is correct
17 Correct 2405 ms 15956 KB Output is correct
18 Correct 2427 ms 15956 KB Output is correct
19 Correct 2396 ms 15960 KB Output is correct
20 Correct 2374 ms 15960 KB Output is correct
21 Correct 2404 ms 15956 KB Output is correct
22 Correct 2501 ms 15956 KB Output is correct
23 Correct 4512 ms 15960 KB Output is correct
24 Correct 4202 ms 15956 KB Output is correct
25 Correct 4380 ms 15956 KB Output is correct
26 Correct 4153 ms 15956 KB Output is correct
27 Correct 4340 ms 15960 KB Output is correct
28 Correct 4217 ms 15960 KB Output is correct
29 Correct 4160 ms 15964 KB Output is correct
30 Correct 252 ms 15956 KB Output is correct
31 Incorrect 1247 ms 18672 KB Output isn't correct
32 Halted 0 ms 0 KB -