115032024-10-14 11:19:12fazekas2028cToronyépítés (1,1,3,3)cpp17Time limit exceeded 26/50301ms31684 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define MOD 20210108

vector<int> dp;

int f(int x) {
	if(dp[x]!=-1)return dp[x]%MOD;
	if(x<3)return f(x-1)*2%MOD;
	else return f(x-1)*2%MOD+f(x-3)*2%MOD;
}

signed main() {
	int n;
	cin >> n;
	dp.resize(n+1, -1);
	dp[0]=1;
	cout<<f(n)%MOD;
	// //dp.resize(n+1)
	// //dp[0]=1;
	// for (int i = 1; i <= n; i++) {
	// 	dp[i]=dp[i-1]*2;
	// 	if(i>=3)dp[i]+=dp[i-3];
	// }
	// cout<<dp[n];
}
SubtaskSumTestVerdictTimeMemory
base26/50
1Accepted0/01ms320 KiB
2Time limit exceeded0/0277ms320 KiB
3Accepted3/31ms320 KiB
4Accepted3/31ms320 KiB
5Accepted4/464ms400 KiB
6Accepted4/41ms320 KiB
7Time limit exceeded0/4301ms31684 KiB
8Time limit exceeded0/4300ms4200 KiB
9Accepted4/41ms508 KiB
10Accepted4/41ms320 KiB
11Time limit exceeded0/4300ms6712 KiB
12Time limit exceeded0/4277ms31288 KiB
13Time limit exceeded0/4301ms27704 KiB
14Time limit exceeded0/4300ms10816 KiB
15Accepted2/21ms320 KiB
16Accepted2/21ms320 KiB