Submission #3,609

2023-03-01 10:12:14

cpp11

Accepted 40/40

3ms

3928 KiB


#include <bits/stdc++.h>

using namespace std;

int main(){


    int n; cin >> n;

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

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

     for (int i = 3; i <= n; i++){
        int x = dp[i-1] + dp[i-2];
        for (int j = i-3; j >= 0; j--) x += 2*dp[j];
        dp.push_back(x);
     }

     cout << dp[n];










    return 0;
}

	Sum	Test	Verdict		Time	Memory
base	40/40
		1	Accepted	0/0	3ms	1888 KiB
		2	Accepted	0/0	3ms	2020 KiB
		3	Accepted	2/2	3ms	2100 KiB
		4	Accepted	2/2	3ms	2232 KiB
		5	Accepted	2/2	3ms	2444 KiB
		6	Accepted	2/2	3ms	2652 KiB
		7	Accepted	2/2	3ms	2768 KiB
		8	Accepted	3/3	3ms	2864 KiB
		9	Accepted	3/3	3ms	3084 KiB
		10	Accepted	3/3	3ms	3288 KiB
		11	Accepted	3/3	3ms	3500 KiB
		12	Accepted	3/3	3ms	3592 KiB
		13	Accepted	3/3	3ms	3592 KiB
		14	Accepted	3/3	3ms	3844 KiB
		15	Accepted	3/3	3ms	3928 KiB
		16	Accepted	3/3	3ms	3812 KiB
		17	Accepted	3/3	2ms	3808 KiB