Submission #783092

#	Time	Username	Problem	Language	Result	Execution time	Memory
783092		minhcool	Kangaroo (CEOI16_kangaroo)	C++17	6 / 100	1 ms	852 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;
    if(n <= 10){
        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";
        return;
    }
    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++){
            if(st_ind != 1 && st_ind != (num - 1)) continue;
            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 <= num; st_ind++){
            if(st_ind != 1 && st_ind != (num - 1)) continue;
            for(int en_ind = 1; en_ind <= num; 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++){
            if(st_ind >= 2 && st_ind < num) continue;
            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 << num << " " << st_ind << " " << en_ind << " " << (g[st_ind][en_ind][0] + g[st_ind][en_ind][1]) % mod << "\n";
            }
        }
    }
    if(st < en) cout << (g[1][en - st + 1][0] + g[1][en - st + 1][1]) % mod << "\n";
    else cout << (g[n][n - (st - en)][0] + g[n][n - (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: 0 / 30
• Subtask 3: 0 / 15
• Subtask 4: 0 / 49