Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("O3", "unroll-loops")
- #include <bits/stdc++.h>
- using namespace std;
- const int inf = 1 << 30;
- const long long MOD = 1e9 + 7;
- typedef long long ll;
- typedef long double ld;
- typedef vector<int> vi;
- typedef pair<int, int> ii;
- typedef vector<ii> vii;
- typedef vector<vi> vvi;
- typedef vector<bool> vb;
- #define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
- #define all(a) a.begin(), a.end()
- #define pb push_back
- #define files(in, out) freopen(in, "r", stdin); freopen(out, "w", stdout)
- #define ppb pop_back
- #define ppf pop_front
- #define fs first
- #define sd second
- #define eb emplace_back
- template<class T> inline void sort(T &a) { sort(all(a)); }
- template<class T> inline T sorted(T a) { sort(a); return a; }
- template<class T> inline istream& operator>>(istream& str, vector<T> &a) { for (auto &i : a) str >> i; return str; }
- void solve() {
- int n;
- cin >> n;
- vector<ll> dp(n);
- if (n == 1) {
- cout << 1;
- return;
- } else if (n == 2) {
- cout << 2;
- return;
- } else if (n == 3) {
- cout << 4;
- return;
- }
- dp[n - 1] = 1;
- dp[n - 2] = 2;
- dp[n - 3] = 4;
- for (int i = n - 4; i >= 0; --i) {
- dp[i] = dp[i + 1] + dp[i + 2] + dp[i + 3];
- }
- cout << dp[0];
- }
- signed main() {
- FAST;
- // files("input.in", "output.out");
- int q = 1;
- // cin >> q;
- while (q--) {
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement