Submission #1287731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287731		AbdullahIshfaq	Binaria (CCO23_day1problem1)	C++20	25 / 25	89 ms	16100 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000003
ll power(ll x, ll n)
{
	ll res = 1;
	x %= MOD;
	while (n)
	{
		if (n & 1)
			res = (res * x) % MOD;
		x = (x * x) % MOD;
		n >>= 1;
	}
	return res;
}
void solve()
{
	ll n, k, c0 = 0, c1 = 0, ans = 1;
	cin >> n >> k;
	vector<ll> a(n - k + 1), b(n, -1);
	for (int i = 0; i < n - k + 1; i++)
	{
		cin >> a[i];
		if (i)
		{
			if (a[i] < a[i - 1])
			{
				b[i - 1] = 1;
				b[i + k - 1] = 0;
			}
			else if (a[i] > a[i - 1])
			{
				b[i - 1] = 0;
				b[i + k - 1] = 1;
			}
		}
	}
	for (ll i = n - 1; i >= 0; i--)
	{
		if (i >= k)
		{
			if (b[i] != -1 and b[i - k] == -1)
			{
				b[i - k] = b[i];
			}
		}
		else
		{
			c1 += b[i] == 1;
			c0 += b[i] == 0;
		}
	}
	for (ll i = 1; i <= a[0] - c1; i++)
	{
		ans = (((ans * power(i, MOD - 2)) % MOD) * (k - c1 - c0 - i + 1)) % MOD;
	}
	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: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 7 / 7