Submission #1150176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150176		dosts	Kangaroo (CEOI16_kangaroo)	C++20	100 / 100	7 ms	328 KiB

kangaroo

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 1e17,N = 3e5+1,MOD = 1e9+7,BL = 1000;

inline int add(int& x,int y) {
    return x = ((x+y >= MOD) ? (x+y-MOD) : x+y);
}

inline int mult(int& x,int y) {
    return x = (x*y)%MOD;
}
void solve() { 
    int n,a,b;
    cin >> n >> a >> b;
    int dp[n+1]{},dp2[n+1]{};
    dp[0] = 1;
    for (int i=0;i<=n;i++) {
        for (int j = 0;j<n;j++) {
            if (!dp[j]) continue;
            if (i==n) continue;
            add(dp2[j+1],dp[j]);
            if (i != a-1 && i != b-1) {
                int select;
                if (i >= a-1 && i >= b-1) select = (j-2)*(j-1)+(i == n-1 && j == 2);
                else if (i >= a-1 || i >= b-1) select = (j-1)*(j-1); 
                else select = j*(j-1);
                if (j >= 2) add(dp2[j-1],mult(dp[j],select));
            }
            else if (i == a-1) add(dp2[j],mult(dp[j],j-(i >= b-1 && i != n-1)));
            else dp2[j] = add(dp2[j],mult(dp[j],j-(i >= a-1 && i != n-1)));
        }
        if (i != n) {
            for (int j = 0;j<n;j++) {
                dp[j] = dp2[j];
                dp2[j] = 0;
            }
        }
    }
    cout << dp[1] << '\n';
}

int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 49 / 49