Submission #622

2021-11-04 20:50:33

cpp14

Accepted 50/50

16ms

9440 KiB

#include <iostream>
#include <vector>

using namespace std;

#define MOD 20210108

int main() {
    int n;
    cin >> n;

    vector<int> dp(n + 1);

    dp[0] = 1;

    for (int i = 1; i <= n; i++) {
        dp[i] = (dp[i - 1] * 2) % MOD;

        if (i >= 3) {
            dp[i] += (dp[i - 3] * 2) % MOD;
            dp[i] %= MOD;
        }
    }

    cout << dp[n] << endl;
}

	Sum	Test	Verdict		Time	Memory
base	50/50
		1	Accepted	0/0	2ms	1740 KiB
		2	Accepted	0/0	1ms	1784 KiB
		3	Accepted	3/3	1ms	1720 KiB
		4	Accepted	3/3	1ms	1724 KiB
		5	Accepted	4/4	1ms	1824 KiB
		6	Accepted	4/4	1ms	1720 KiB
		7	Accepted	4/4	16ms	9440 KiB
		8	Accepted	4/4	3ms	2552 KiB
		9	Accepted	4/4	1ms	1824 KiB
		10	Accepted	4/4	1ms	1720 KiB
		11	Accepted	4/4	4ms	3200 KiB
		12	Accepted	4/4	16ms	9440 KiB
		13	Accepted	4/4	14ms	8404 KiB
		14	Accepted	4/4	6ms	4244 KiB
		15	Accepted	2/2	1ms	1828 KiB
		16	Accepted	2/2	1ms	1724 KiB