Submission #70013

#	Time	Username	Problem	Language	Result	Execution time	Memory
70013		yogahmad	Asceticism (JOI18_asceticism)	C++14	49 / 100	145 ms	142136 KiB

asceticism

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fbo find_by_order
#define ook order_of_key
#define f first
#define s second
#define pb push_back
#define reset(a,b) memset(a,b,sizeof a);
#define MOD 1000000007
#define MID (l+r)/2
#define ALL(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define mx 3003
#define pc(x) putchar_unlocked(x);
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> pbds;

long long dep[mx][mx],n,k;

long long dp(int n,int k){
	if(k>=n)return 0;
	if(k==0 || k==n-1)return 1;
	long long&ret=dep[n][k];
	if(ret!=-1)return ret;
	ret=0;
	ret=1LL*(n-k)*dp(n-1,k-1)%MOD+1LL*(k+1)*dp(n-1,k)%MOD;
	ret%=MOD;
	//cout<<n<<' '<<k<<' '<<ret<<endl;
	return ret;
}

int main(){
	reset(dep,-1);
	cin>>n>>k;
	cout<<dp(n,k-1)<<endl;
}

• Subtask 1: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 0 / 51