Submission #701899

#	Time	Username	Problem	Language	Result	Execution time	Memory
701899		gupta_nitin	Kangaroo (CEOI16_kangaroo)	C++14	0 / 100	12 ms	31572 KiB

kangaroo

#include <bits/stdc++.h>

typedef long double ld;
#define int long long

#define gcd            __gcd
#define endl           "\n"
#define setbits(x)     __builtin_popcountll(x)
#define zrobits(x)     __builtin_ctzll(x)
#define mod            1000000007
#define mod2           998244353
#define maxe           *max_element
#define mine           *min_element
#define inf            1e18
#define pb             push_back
#define all(x)         x.begin(), x.end()
#define f              first
#define s              second
#define sz(x)          (int)(x).size()
#define deci(x, y)     fixed<<setprecision(y)<<x
#define w(t)           int t; cin>>t; while(t--)
#define nitin          ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define PI             3.141592653589793238
#define mem0(x)        memset(x,0,sizeof x)
#define mem1(x)        memset(x,-1,sizeof x)
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.f << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }

#ifdef NITIN
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

/*
 think about hashing while comparing contiguous elements...
 try to think backward..
 if you arent able to come up for answer, try to fix some variable, some bits, initial starting point or end point.....
 may be break a operation into two or combine two into one
*/
int n;
int s, e;
int dp[2001][2001];
int solve(int idx,int comp) {
    if (idx == n + 1) {
        return comp == 1;
    }
    if (dp[idx][comp] != -1) return dp[idx][comp];
    int tot = 0;
    if (idx != s && idx != e) {
        //ek naya component
        if (comp + 1 - (idx > s) - (idx > e) > 0)
            tot += (solve(idx + 1, comp + 1) * (comp + 1 - (idx > s) - (idx > e))) % mod;
        tot %= mod;

        //add two component
        if (comp >= 2) tot += (solve(idx + 1, comp - 1) * (comp - 1)) % mod;
        tot %= mod;
    } else if (idx == s) {
        //ek naya component
        tot += solve(idx + 1, comp + 1);
        tot %= mod;

        //add to first component
        if (comp >= 1) tot += (solve(idx + 1, comp)) % mod;
        tot %= mod;
    } else if (idx == e) {
        //ek naya component
        tot += solve(idx + 1, comp + 1);
        tot %= mod;

        //add to last component
        if (comp >= 1) tot += (solve(idx + 1, comp)) % mod;
        tot %= mod;
    }
    return dp[idx][comp] = tot;
}

void solve() {
    ifstream cin;
    cin.open("kangaroo.in");
    cin >> n;
    cin >> s >> e;
    cin.close();
    memset(dp,-1,sizeof dp);
    int ans = solve(2, 1);
    ofstream cout;
    cout.open("kangaroo.out");
    cout << ans << endl;
    cout.close();
}

int32_t main() {
    nitin;

    solve();
}

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