Quick actions

cmd+k|ctrl+k

Navigation

Languages

CF_722_B

Snippet info

Language

Cpp

Visibility

public

Author

karthik.pasupulatei

Created

2021-06-08T14:00:10.42017Z

Updated

2021-06-17T05:39:00.243981Z

// Problem: B. Kavi on Pairing Duty
// Contest: Codeforces - Codeforces Round #722 (Div. 1)
// URL: https://codeforces.com/contest/1528/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include "bits/stdc++.h"
using namespace std; 
using ll = long long;

#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const ll mod = 998244353, maxn = 2e5 + 5;
inline ll add(ll a, ll b, ll m = mod) { return (((a % m) + (b % m)) % m); }

using namespace std ; 


ll dp[1000001] ; 
ll  jumps( ll  N  ){
	if( N  == 1 || N == 0 )return 1LL; 
	if(dp[N] == - 1){
		ll retVal  =  0 ; 
		for(ll i = N-1  ; i > -1 ; i--){
			retVal  = add(retVal , jumps(i)) ; 
		}
		dp[N] = add(retVal ,1LL) ;
	}
	return dp[N] ; 
}
int main(){
    FIO
    ll n ; 
	cin>>  n ; 
	memset(dp , -1 ,sizeof(dp)) ; 
	cout <<  jumps(n) << "\n" ; 
    return 0 ; 
}
INFO