제출 #81744

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
81744		Saboon	캥거루 (CEOI16_kangaroo)	C++14	51 / 100	419 ms	7196 KiB

kangaroo

#include <iostream>
#include <sstream>
#include <queue>
#include <stack>
#include <vector>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <iomanip>
#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int maxn = 200 + 37;
const int mod = 1e9 + 7;

ll dp[maxn][maxn][3];

ll fen[maxn + 100][maxn][3];

ll get (int idx, int w, int d) {
    if (idx < 0)
        return 0;
    ll ret = 0;
    for (; idx; idx -= idx & -idx)
        ret = (ret + fen[idx][w][d]) % mod;
    return ret;
}

ll sum (int l, int r, int w, int d) {
    return (get (r - 1, w, d) - get (l - 1, w, d) + mod) % mod;
}

void change (int idx, ll val, int w, bool d) {
    for (; idx < maxn; idx += idx & -idx)
        fen[idx][w][d] = (fen[idx][w][d] + val) % mod;
}

int main() {
    ios_base::sync_with_stdio(false);
    int n, s, t;
    cin >> n >> s >> t;
    change (1, 1, 2, 1);
    change (2, 1, 1, 0);
    for (int i = 3; i <= n; i++) {
        for (int st = 1; st <= i; st ++) {
            for (int en = 1; en <= i; en ++) {
                if (st != en) {
                    if (en > st) {
                        dp[st][en][1] = sum (st, i, en - 1, 0);
//                      dp[i][st][en][1] = (dp[i][st][en][1] + par[i - 1][i - 1][en - 1][0] - par[i - 1][st - 1][en - 1][0] + mod + mod) % mod;
                        dp[st][en][0] = sum (0, st, en - 1, 1);
//                      dp[i][st][en][0] = (dp[i][st][en][0] + par[i - 1][st - 1][en - 1][1]) % mod;
                    }
                    else {
                        dp[st][en][1] = sum (st, i, en, 0);
//                      dp[i][st][en][1] = (dp[i][st][en][1] + par[i - 1][i - 1][en][0] - par[i - 1][st - 1][en][0] + mod + mod) % mod;
                        dp[st][en][0] = sum (0, st, en, 1);
//                      dp[i][st][en][0] = (dp[i][st][en][0] + par[i - 1][st - 1][en][1] + mod) % mod;
                    }
//                  cout << i << " " << st << " " << en << " right " << dp[i][st][en][1] << endl;
//                  cout << i << " " << st << " " << en << " left " << dp[i][st][en][0] << endl;
                }
            }
        }
        memset (fen, 0, sizeof fen);
        for (int st = 1; st <= i; st ++) {
            for (int en = 1; en <= i; en ++) {
                change (st, dp[st][en][1], en, 1);
                change (st, dp[st][en][0], en, 0);
            }
        }
    }
    cout << (dp[s][t][1] + dp[s][t][0]) % mod << endl;
}

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