Submission #1271763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271763		cbnk32_tuandung	Zapina (COCI20_zapina)	C++17	110 / 110	252 ms	7380 KiB

zapina

/*  _  _   ___   __  ___  ___  _  _  ___  __   ___     _   _  ___   ___  __   _____  _  _  ___       */
/* | || | /_\ \ / / / __|/ _ \| \| |/ __| \ \ / /_\   | | | |/ _ \ / __| \ \ / / _ \| \| |/ __|      */
/* | __ |/ _ \ V /  \__ \ (_) | .` | (_ |  \ V / _ \  | |_| | (_) | (__   \ V / (_) | .` | (_ |      */
/* |_||_/_/_\_\_|___|___/\___/|_|\_|\___|   \_/_/_\_\ _\___/ \___/ \___| _ \_/_\___/|_|\_|\___| ___  */
/* |   \| __| |_   _| || | /_\ \ / / |   \ / _ \_ _| |  \/  | __| \| | || | |  \/  |/ _ \| \| |/ __| */
/* | |) | _|    | | | __ |/ _ \ V /  | |) | (_) | |  | |\/| | _|| .` | __ | | |\/| | (_) | .` | (_ | */
/* |___/|___|   |_| |_||_/_/ \_\_|   |___/ \___/___| |_|  |_|___|_|\_|_||_| |_|  |_|\___/|_|\_|\___| */

#include <bits/stdc++.h>
using namespace std;

/*
 
 run
 g++ coci1920_r5_zapina.cpp -o run.exe && ./run.exe
 g++ coci1920_r5_zapina.cpp -std=c++1y -o run.exe && ./run.exe
 
 */

#define re exit(0)
#define r0 return 0
#define ll long long
#define ull unsigned long long
#define TASK "."

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

constexpr int MOD = 1000000007;
constexpr int MAX_N = 700 + 5;

template<typename T> void minimise(T &abc, T xyz) {
    if (abc > xyz) abc = xyz;
}

template<typename T> void maximise(T &abc, T xyz) {
    if (abc < xyz) abc = xyz;
}

template<typename T> void add(T &abc, T xyz) {
    abc += xyz;
    if (abc >= MOD) abc -= MOD;
    if (abc < 0) abc += MOD;
}

void fileIO() {
    freopen(TASK".INP", "r", stdin);
    freopen(TASK".OUT", "w", stdout);
}

int N;
ll dp[MAX_N][MAX_N][2];
ll C[MAX_N][MAX_N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    // fileIO();

    cin >> N;
    for (int i = 0; i < MAX_N; ++i) {
        C[i][i] = 1;
        C[i][0] = 1;
    }
    for (int i = 1; i < MAX_N; ++i) {
        for (int j = 1; j < i; ++j) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
        }
    }
    for (int i = 0; i <= N; ++i) {
        dp[0][i][0] = 1;
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            for (int x = 0; x <= i; ++x) {
                int cur = i - x;
                if (cur == j) {
                    add(dp[i][j][1], ((dp[x][j - 1][0] + dp[x][j - 1][1]) * C[i][cur]) % MOD);
                } else {
                    add(dp[i][j][0], (dp[x][j - 1][0] * C[i][cur]) % MOD);
                    add(dp[i][j][1], (dp[x][j - 1][1] * C[i][cur]) % MOD);
                }
            }
        }
    }
    cout << dp[N][N][1];

    cerr << "\nTime elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s.";
    r0;
}

/*
 Rubi-channnnn~~~
 Haiiii~~~
 Nani ga suki?
 Choco minto... yori mo anata~
 
 Ayumu-channnnn~~~
 Haiiiii~~~
 Nani ga suki?
 Suturuberi fureiba yori mo anata~
 
 Shiki-channnn~~~
 Haiiiii~~~~
 Nani ga suki?
 Kukkie ando krimu yori mo anata~
 
 Minaaaa~~~
 Haiiiiii~~~
 Nani ga suki?
 Mochrion daisuki AI♡SCREAM
*/

Compilation message (stderr)

zapina.cpp: In function 'void fileIO()':
zapina.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     freopen(TASK".INP", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zapina.cpp:49:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     freopen(TASK".OUT", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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