Submission #12,853

2025-01-02 14:36:15

cpp17

Accepted 50/50

7ms

572 KiB

#include <iostream>

using namespace std;

const int MOD = 20210108;

int main()
{
    int N;
    cin >> N;
    long long dp[4];
    dp[0] = 1;
    dp[1] = 2;
    dp[2] = 4;
    for(int i = 3; i <= N; i++){
        dp[3] = (2*dp[2] + 2*dp[0])%MOD;
        dp[0] = dp[1];
        dp[1] = dp[2];
        dp[2] = dp[3];
    }
    if(N <= 2){
        cout << dp[N] << endl;
    }
    else{
        cout << dp[3] << endl;
    }
    return 0;
}

	Sum	Test	Verdict		Time	Memory
base	50/50
		1	Accepted	0/0	1ms	572 KiB
		2	Accepted	0/0	1ms	320 KiB
		3	Accepted	3/3	1ms	320 KiB
		4	Accepted	3/3	1ms	320 KiB
		5	Accepted	4/4	1ms	500 KiB
		6	Accepted	4/4	1ms	320 KiB
		7	Accepted	4/4	7ms	320 KiB
		8	Accepted	4/4	2ms	392 KiB
		9	Accepted	4/4	1ms	552 KiB
		10	Accepted	4/4	1ms	320 KiB
		11	Accepted	4/4	2ms	320 KiB
		12	Accepted	4/4	7ms	320 KiB
		13	Accepted	4/4	6ms	404 KiB
		14	Accepted	4/4	3ms	404 KiB
		15	Accepted	2/2	1ms	332 KiB
		16	Accepted	2/2	1ms	320 KiB