Submission #1228469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228469		a4n_	Asceticism (JOI18_asceticism)	C++20	49 / 100	66 ms	117832 KiB

asceticism

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
#define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
 
const int N = 5e5 + 100, lg = 18;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;
 
ll MOD(ll a, ll mod=Mod) {
    a%=mod; (a<0)&&(a+=mod); return a;
}
ll poww(ll a, ll b, ll mod=Mod) {
    ll res = 1;
    while(b > 0) {
        if(b%2 == 1) res = MOD(res * a, mod);
        b /= 2;
        a = MOD(a * a, mod);
    }
    return res;
}
 
ll n, k;
ll dp[5005][5005];
void work() {
    cin>>n>>k;

    dp[1][1] = 1;
    for(ll i=2; i<=n; i++) {
        for(ll j=1; j<=i; j++) {
            dp[i][j] = MOD(dp[i-1][j] * j + dp[i-1][j-1] * (i - j + 1));
        }
    }

    cout<<dp[n][k]<<endl;
}

void reset_work() {
    return;
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
 
    // cin>>t;
    int tc = 1;
    while(tc --) {
        work();
        reset_work();
    }
 
    return 0;
}

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