Submission #1150172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150172		dosts	Kangaroo (CEOI16_kangaroo)	C++20	100 / 100	30 ms	31756 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;

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

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