Beküldés #2 905

2023-02-02 13:21:08

cpp11

Elfogadva 50/50

18ms

16364 KiB

#include <bits/stdc++.h>

using namespace std;

const int MOD = 20210108;

int main(){


    int n; cin >> n;
    vector<int> dp = {1, 2, 4};

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

    cout << dp[n];

    // dp(n) = 2*dp(n-1) + 2*dp(n-3)

    return 0;
}

	Összpont	Teszt	Verdikt		Idő	Memória
base	50/50
		1	Elfogadva	0/0	3ms	1960 KiB
		2	Elfogadva	0/0	3ms	2136 KiB
		3	Elfogadva	3/3	3ms	2332 KiB
		4	Elfogadva	3/3	2ms	2400 KiB
		5	Elfogadva	4/4	2ms	2612 KiB
		6	Elfogadva	4/4	3ms	2708 KiB
		7	Elfogadva	4/4	18ms	15336 KiB
		8	Elfogadva	4/4	4ms	5032 KiB
		9	Elfogadva	4/4	3ms	3356 KiB
		10	Elfogadva	4/4	3ms	3520 KiB
		11	Elfogadva	4/4	6ms	6852 KiB
		12	Elfogadva	4/4	17ms	16096 KiB
		13	Elfogadva	4/4	17ms	16364 KiB
		14	Elfogadva	4/4	7ms	7176 KiB
		15	Elfogadva	2/2	3ms	4104 KiB
		16	Elfogadva	2/2	2ms	4176 KiB