oj.uz

Submission #603211

# Submission time Handle Problem Language Result Execution time Memory
603211 2022-07-23T17:10:19 Z MohamedAhmed04 Uplifting Excursion (BOI22_vault) C++14
0 / 100
 2499 ms 32080 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()
	{
		if(!q.size())
			while(1) ;
		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 , 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(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 62 ms 15956 KB Output is correct
2 Correct 89 ms 15956 KB Output is correct
3 Correct 38 ms 15940 KB Output is correct
4 Correct 317 ms 15956 KB Output is correct
5 Runtime error 2499 ms 32080 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 15956 KB Output is correct
2 Correct 89 ms 15956 KB Output is correct
3 Correct 38 ms 15940 KB Output is correct
4 Correct 317 ms 15956 KB Output is correct
5 Runtime error 2499 ms 32080 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 15956 KB Output is correct
2 Incorrect 1375 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 309 ms 15956 KB Output is correct
2 Incorrect 1375 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 309 ms 15956 KB Output is correct
2 Incorrect 1375 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 62 ms 15956 KB Output is correct
2 Correct 89 ms 15956 KB Output is correct
3 Correct 38 ms 15940 KB Output is correct
4 Correct 317 ms 15956 KB Output is correct
5 Runtime error 2499 ms 32080 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 15956 KB Output is correct
2 Incorrect 1375 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 62 ms 15956 KB Output is correct
2 Correct 89 ms 15956 KB Output is correct
3 Correct 38 ms 15940 KB Output is correct
4 Correct 317 ms 15956 KB Output is correct
5 Runtime error 2499 ms 32080 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 15956 KB Output is correct
2 Incorrect 1375 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 62 ms 15956 KB Output is correct
2 Correct 89 ms 15956 KB Output is correct
3 Correct 38 ms 15940 KB Output is correct
4 Correct 317 ms 15956 KB Output is correct
5 Runtime error 2499 ms 32080 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -