제출 #701901

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
701901		gupta_nitin	캥거루 (CEOI16_kangaroo)	C++14	100 / 100	46 ms	31900 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[2005][2005];
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
        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
        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: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 49 / 49