Submission #3287299

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int a[222222];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	vector<int> vec; ll ans = 0;
	for(int i=0;i<n;i++)
	{
		if(vec.empty()||a[i]>=vec.back())
		{
			vec.pb(a[i]); 
			continue;
		}
		int mn = int(1e9); int aft = i-1; int x = 0;
		for(int j=i-1;j>=-1;j--)
		{
			int val = i - 1 - j + max(0, (j>=0?vec[j]:-int(1e9)) - a[i]);
			if(val<mn)
			{
				mn=val; aft=j; x = max(0, (j>=0?vec[j]:-int(1e9)) - a[i]);
			}
		}
		vi nw; ans += mn;
		for(int j=0;j<=aft;j++) nw.pb(vec[j]);
		nw.pb(a[i]+x);
		for(int j=aft+1;j<i;j++) nw.pb(vec[j]);
		vec=nw;
	}
	cout<<ans<<'\n';
}

Submission Info

Judge Result