Submission #783064

#	Time	Username	Problem	Language	Result	Execution time	Memory
783064		minhcool	Kangaroo (CEOI16_kangaroo)	C++17	51 / 100	2066 ms	111976 KiB

kangaroo

#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e2 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

int n, st, en, dp[N][N][N][2];

void add(int &a, int b){
    a = (a + b) % mod;
}

#ifdef local
void process(){
    cin >> n >> st >> en;
    dp[2][1][2][0] = dp[2][2][1][1] = 1;
    for(int num = 3; num <= n; num++){
        for(int st_ind = 1; st_ind <= num; st_ind++){
            for(int en_ind = 1; en_ind <= num; en_ind++){
                if(st_ind == en_ind) continue;
                for(int lst = 1; lst < en_ind; lst++){
                    if(lst == st_ind) continue;
                    // we are deleting en_ind
                    add(dp[num][st_ind][en_ind][0], dp[num - 1][st_ind - (st_ind > en_ind)][lst][1]);
                }
                for(int lst = en_ind + 1; lst <= num; lst++){
                    if(lst == st_ind) continue;
                    // we are deleting en_ind
                    add(dp[num][st_ind][en_ind][1], dp[num - 1][st_ind - (st_ind > en_ind)][lst - 1][0]);
                }
            }
        }
    }
    cout << (dp[n][st][en][0] + dp[n][st][en][1]) % mod;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    //freopen("abc.inp", "r", stdin);
    //freopen("abc.out", "w", stdout);
	process();
}
#endif

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