Submission #1287771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287771		AbdullahIshfaq	Line Town (CCO23_day1problem3)	C++20	6 / 25	33 ms	19936 KiB

Main

#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();
	}
}

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 0 / 3
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 3
• Subtask 7: 0 / 2
• Subtask 8: 0 / 3