Submission #1097182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097182		raphaelp	Binaria (CCO23_day1problem1)	C++14	25 / 25	188 ms	28752 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6;
long long fac[MAXN + 1];
long long inv[MAXN + 1];
long long exp(long long x, long long n, long long m)
{
    x %= m;
    long long ans = 1;
    while (n > 0)
    {
        if (n % 2)
            ans = (ans * x) % m;
        n /= 2;
        x = (x * x) % m;
    }
    return ans;
}
void precalc(long long p)
{
    fac[0] = 1;
    for (int i = 1; i <= MAXN; i++)
    {
        fac[i] = (fac[i - 1] * i) % p;
    }
    inv[MAXN] = exp(fac[MAXN], p - 2, p);
    for (int i = MAXN; i >= 1; i--)
        inv[i - 1] = (inv[i] * i) % p;
}
long long choose(int n, int k, int p)
{
    return ((fac[n] * inv[k]) % p * inv[n - k]) % p;
}
int main()
{
    precalc(1000003);
    int N, K;
    cin >> N >> K;
    vector<int> Tab(N - K + 1);
    for (int i = 0; i < N - K + 1; i++)
    {
        cin >> Tab[i];
    }
    vector<int> val(N, -1);
    for (int i = 1; i < N - K + 1; i++)
    {
        if (Tab[i] == Tab[i - 1])
            val[i + K - 1] = val[i - 1];
        if (Tab[i] > Tab[i - 1])
            val[i + K - 1] = 1;
        if (Tab[i] < Tab[i - 1])
            val[i + K - 1] = 0;
    }
    int a = Tab.back(), b = K;
    for (int i = N - K; i < N; i++)
    {
        if (val[i] == 1)
        {
            a--;
            b--;
        }
        if (val[i] == 0)
            b--;
    }
    cout << choose(b, a, 1000003);
}

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