Submission #3,828

2023-03-03 10:38:43

cpp14

Accepted 50/50

18ms

10768 KiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll MOD = 20210108;

int add(int a, int b){
    return (a + b) % MOD;
}

int main()
{
    int n;
    cin >> n;
    vector<int> dp(max(3, n+1), 0);
    dp[0] = 1;
    dp[1] = 2;
    dp[2] = 4;
    for (int i=3; i<=n; i++){
        dp[i] = add(add(dp[i-1], dp[i-1]), add(dp[i-3], dp[i-3]));
    }
    cout << dp[n];
}

	Sum	Test	Verdict		Time	Memory
base	50/50
		1	Accepted	0/0	3ms	1684 KiB
		2	Accepted	0/0	2ms	1936 KiB
		3	Accepted	3/3	2ms	2012 KiB
		4	Accepted	3/3	3ms	2252 KiB
		5	Accepted	4/4	3ms	2352 KiB
		6	Accepted	4/4	2ms	2468 KiB
		7	Accepted	4/4	18ms	10332 KiB
		8	Accepted	4/4	4ms	3660 KiB
		9	Accepted	4/4	2ms	2796 KiB
		10	Accepted	4/4	3ms	2920 KiB
		11	Accepted	4/4	6ms	4396 KiB
		12	Accepted	4/4	17ms	10768 KiB
		13	Accepted	4/4	17ms	9804 KiB
		14	Accepted	4/4	8ms	5644 KiB
		15	Accepted	2/2	2ms	3388 KiB
		16	Accepted	2/2	3ms	3596 KiB