Submission #1264153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264153		mohammadsam	Kangaroo (CEOI16_kangaroo)	C++20	100 / 100	126 ms	94728 KiB

kangaroo

/*
    in the name of god
*/
//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")

#include <bits/stdc++.h>

using namespace std;
#define int long long 
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll ;

#define File          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define all(V)        V.begin(),V.end()
#define setprec(x)    fixed << setprecision(x)
#define Mp(a,b)       make_pair(a,b)
#define len(V)        (int)(V.size())
#define sep           ' '
#define endl          '\n'
#define pb            push_back
#define fi            first
#define sec           second
#define popcount(x)   __builtin_popcount(x)
#define lid           u<<1
#define rid           (lid)|1
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 2e3 + 10,SQ=320,LOG=31;
const ll inf = 2e9 , MD = 1e9 + 7;

inline ll md(ll x){ x %= MD; return (x < 0 ? x + MD : x);}
int n ;
int s,e;
int dp[N][N][3];
int32_t main() {
    ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);
    cin >> n >> s >> e;
    dp[0][0][0] = 1;
    for(int i = 0;i < n;i++){
        for(int j = 0;j<n;j++){
            for(int r =0 ;r < 3;r++){
                if((i+1) == s || (i+1) == e){
                    if(r + 1 < 3) {
                        if(j) dp[i+1][j][r+1] = md(dp[i+1][j][r+1] + dp[i][j][r]);
                        dp[i+1][j+1][r+1] = md(dp[i+1][j+1][r+1] + dp[i][j][r]);
                    }
                }
                else{
                    dp[i+1][j+1][r] = md(dp[i+1][j+1][r] + md((j+1-r) * dp[i][j][r]));
                    if(j >= 2) dp[i+1][j-1][r] = md(dp[i+1][j-1][r] + md((j-1) * dp[i][j][r]));
                }
            }
        }
    }
    cout << dp[n][1][2] << endl;
    return 0;
}

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