Submission #1284891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284891		hrantsargsyan	Zapina (COCI20_zapina)	C++20	0 / 110	6 ms	7228 KiB

zapina

#include <iostream>

using namespace std;

const int N = 1005;

long long dp[N][N][2];
long long C[N][N];
long long mod = 1e9 + 7;

long long add(long long a, long long b)
{
    a %= mod; b %= mod;
    long long res = a + b;
    if (res >= mod) res -= mod;
    return res;
}
long long mult(long long x, long long y)
{
    return (x % mod) * (y % mod) % mod;
}

void precalcC() {
    for (int n = 0; n <= N; n++) {
        C[n][0] = C[n][n] = 1;
        for (int k = 1; k < n; k++)
            C[n][k] = add(C[n - 1][k - 1], C[n - 1][k]);
    }
}

int main()
{
    int n;
    cin >> n;
    precalcC();
    dp[1][1][1] = 1;
    dp[1][0][0] = 1;
    dp[1][1][0] = 0;
    for (int i = 2;i <= n;++i)
    {
        dp[1][i][0] = 1;
    }
    for (int i = 1;i <= n;++i)
    {
        for (int j = 0;j <= n;++j)
        {
            for (int k = 0;k <= j;++k)
            {
                int x = C[j][k];
                if (k != i)
                {
                    dp[i][j][0] = add(dp[i][j][0], mult(dp[i - 1][j - k][0], x));
                }
                else
                {
                    dp[i][j][1] = add(dp[i][j][1], mult(dp[i-1][j - k][0], x));
                }
                dp[i][j][1] = add(dp[i][j][1], mult(dp[i-1][j - k][1], x));
            }
        }
    }
    //for (int i = 1;i <= n;++i)
    //{
    //    for (int j = 0;j <= n;++j)
    //    {
    //        cout << i << " people " << j << " tasks." << endl;
    //        cout << dp[i][j][1] << " Happy " << endl;
    //        cout << dp[i][j][0] << " uhappy " << endl;
    //    }
    //}
    cout << dp[n][n][1] << endl;
}

Compilation message (stderr)

zapina.cpp: In function 'void precalcC()':
zapina.cpp:25:27: warning: iteration 1005 invokes undefined behavior [-Waggressive-loop-optimizations]
   25 |         C[n][0] = C[n][n] = 1;
      |                   ~~~~~~~~^~~
zapina.cpp:24:23: note: within this loop
   24 |     for (int n = 0; n <= N; n++) {
      |                     ~~^~~~

• Subtask 1: 0 / 22
• Subtask 2: 0 / 33
• Subtask 3: 0 / 55