Submission #526298

#	Time	Username	Problem	Language	Result	Execution time	Memory
526298		Jeff12345121	Kangaroo (CEOI16_kangaroo)	C++14	51 / 100	845 ms	129728 KiB

kangaroo

#include <bits/stdc++.h>
#define int long long
using namespace std;

#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#else
#define in cin
#define out cout
#endif

const int nmax = 205,mod = 1000000007;
int n,cs,cf,dp[nmax][nmax][nmax][2],viz[nmax][nmax][nmax][2];///third means on which position from left to right is the cf, NOT CONSIDERING
///current one
struct wow {
    int l,r,pos,dir;
};
queue<wow> q;
int ans = 0;
void addSelf(int &a, int b) {
    a = (a + b) % mod;
}
void extend(int l, int r,int pos, int dir) {
    int low,high;
    if (dir == 0) {
        low = 0; /// how many there are left of this guy
        high = l - 1; /// same
    } else {
        low = l;
        high = l + r - 1;
    }
    for (int newLeft = low; newLeft <= high; newLeft++) {
        int newRight = l + r - newLeft - 1;
        int newPos;
        if (newLeft + 1 < pos) {/// this is left of the target
            newPos = pos - 1;
        } else if (newLeft + 1 == pos){
            if (newLeft + newRight == 0) {
                addSelf(ans, dp[l][r][pos][dir]);
            }
            continue;
        } else {
            newPos = pos;
        }
        int newDir = 1 - dir;
        addSelf(dp[newLeft][newRight][newPos][newDir] , dp[l][r][pos][dir]);
        if (viz[newLeft][newRight][newPos][newDir] == 0) {
            q.push({newLeft, newRight, newPos, newDir});
            viz[newLeft][newRight][newPos][newDir] = 1;
        }
    }
}
int32_t main() {
    in >> n >> cs >> cf;
    //dp is all 0 init, dp[st][dr][dir you will go now 0 = st, 1 = dr] = number of ways to get here
    int l,r,pos;

    if (cs <= cf) {
        l = cs - 1;
        r = n - cs;
        pos = cf - 1;
    } else {
        l = cs - 1;
        r = n - cs;
        pos = cf;
    }

    dp[l][r][pos][0] = dp[l][r][pos][1] = 1;
    q.push({l, r, pos,0});
    q.push({l, r, pos,1});
    ans = 0;
    while(!q.empty()) {
        int l = q.front().l;
        int r = q.front().r;
        int pos = q.front().pos;
        int dir = q.front().dir;
        q.pop();
        extend(l,r,pos,dir);
    }

    out << ans << "\n";
}

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