제출 #1287771

#제출 시각아이디문제언어결과실행 시간메모리
1287771AbdullahIshfaqLine Town (CCO23_day1problem3)C++20
6 / 25
33 ms19936 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000003
const int N = 500005;
ll n, h[N], s1[N], s2[N], f[N], g[N], ans = 1e18;
void solve()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> h[i];
	}
	for (int i = 0; i <= n + 1; i++)
	{
		f[i] = g[i] = 1e18;
	}
	f[0] = 0;
	for (int i = 1; i <= n; i++)
	{
		f[i] = f[i - 1];
		s1[i] = s1[i - 1];
		if (h[i] == 1)
		{
			if (i & 1)
			{
				s1[i]++;
				if (s1[i - 1] >= 0)
				{
					f[i] -= i;
				}
				else
				{
					f[i] += i;
				}
			}
			else
			{
				s1[i]--;
				if (s1[i - 1] <= 0)
				{
					f[i] -= i;
				}
				else
				{
					f[i] += i;
				}
			}
		}
	}
	g[n + 1] = 0;
	for (int i = n; i >= 1; i--)
	{
		g[i] = g[i + 1];
		s2[i] = s2[i + 1];
		if (h[i] == -1)
		{
			if (i & 1)
			{
				s2[i]++;
				if (s2[i + 1] >= 0)
				{
					g[i] += i;
				}
				else
				{
					g[i] -= i;
				}
			}
			else
			{
				s2[i]--;
				if (s2[i + 1] <= 0)
				{
					g[i] += i;
				}
				else
				{
					g[i] -= i;
				}
			}
		}
	}
	for (int i = 0; i <= n; i++)
	{
		if (s1[i] == 0 and s2[i + 1] == 0)
		{
			ans = min(ans, f[i] + g[i + 1]);
		}
	}
	if (ans == 1e18)
	{
		ans = -1;
	}
	cout << ans << "\n";
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll t = 1;
	// cin >> t;
	for (int i = 1; i <= t; i++)
	{
		solve();
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...