Submission #3969918


Source Code Expand

Copy
	#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

#include <ext/rope>

 

#define ll long long

#define pb push_back

#define sz(x) (int)(x).size()

#define mp make_pair

#define all(x) x.begin(), x.end()

 

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<ll> stk;
	while(n--)
	{
		ll a;
		cin >> a;
		//cout << a << endl;
		stk.push_back(a);
		int q=stk.size();
		while(q>2&&stk[q-1]<=stk[q-2]&&stk[q-3]<=stk[q-2])
		{
			ll ne=stk[q-1]+stk[q-3]-stk[q-2];
			for(int i=0;i<3;i++)
			stk.pop_back();
			stk.push_back(ne);
			q-=2;
		}
	}
	ll sum=0;
	deque<ll> q;
	for(auto p:stk)
	q.push_back(p);
	int z=1;
	while(q.size())
	{
		if(q.front()>=q.back())
		{
			sum+=q.front()*z;
			q.pop_front();
		}
		else
		{
			sum+=q.back()*z;
			q.pop_back();
		}
		z*=-1;
	}
	cout << sum;
}
    

Submission Info

Submission Time
Task L - Deque
User nikolapesic2802
Language C++14 (GCC 5.4.1)
Score 100
Code Size 922 Byte
Status
Exec Time 3 ms
Memory 256 KB

Test Cases

Set Name Score / Max Score Test Cases
All 100 / 100 0_00, 0_01, 0_02, 0_03, 0_04, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13
Case Name Status Exec Time Memory
0_00 1 ms 256 KB
0_01 1 ms 256 KB
0_02 1 ms 256 KB
0_03 1 ms 256 KB
0_04 1 ms 256 KB
1_00 1 ms 256 KB
1_01 1 ms 256 KB
1_02 2 ms 256 KB
1_03 3 ms 256 KB
1_04 2 ms 256 KB
1_05 2 ms 256 KB
1_06 3 ms 256 KB
1_07 3 ms 256 KB
1_08 3 ms 256 KB
1_09 3 ms 256 KB
1_10 3 ms 256 KB
1_11 3 ms 256 KB
1_12 3 ms 256 KB
1_13 3 ms 256 KB