Submission #783075

#	Time	Username	Problem	Language	Result	Execution time	Memory
783075		minhcool	Kangaroo (CEOI16_kangaroo)	C++17	51 / 100	2050 ms	23684 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 = 2e3 + 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;
int f[N][N][2], g[N][N][2], pref[N][N][2];
//dp[N][N][N][2];

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

#ifdef local
void process(){
    cin >> n >> st >> en;
    g[1][2][0] = g[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++){
                f[st_ind][en_ind][0] = g[st_ind][en_ind][0];
                f[st_ind][en_ind][1] = g[st_ind][en_ind][1];
                g[st_ind][en_ind][0] = g[st_ind][en_ind][1] = 0;
            }
        }
        for(int st_ind = 1; st_ind <= n; st_ind++){
            for(int en_ind = 1; en_ind <= n; en_ind++){
                pref[st_ind][en_ind][0] = pref[st_ind][en_ind - 1][0];
                add(pref[st_ind][en_ind][0], f[st_ind][en_ind][0]);
                pref[st_ind][en_ind][1] = pref[st_ind][en_ind - 1][1];
                add(pref[st_ind][en_ind][1], f[st_ind][en_ind][1]);
            }
        }
        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;
                int temp = st_ind - (st_ind > en_ind);
                g[st_ind][en_ind][0] = pref[temp][en_ind - 1][1];
                g[st_ind][en_ind][1] = (pref[temp][num - 1][0] - pref[temp][en_ind - 1][0] + mod) % mod; 
                /*
                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 << (g[st][en][0] + g[st][en][1]) % mod << "\n";
    //cout << (double)clock() / (double)CLOCKS_PER_SEC << "\n";
}

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