제출 #56564

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56564		Benq	캥거루 (CEOI16_kangaroo)	C++14	100 / 100	145 ms	52456 KiB

kangaroo

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 2005;

int N,cs,cf;
int A[MX][MX], a[MX][MX];
int AA[MX][MX], aa[MX][MX];
int D[MX][MX], d[MX][MX];

int ad(int a, int b) { return (a+b)%MOD; }
int sub(int a, int b) { return (a-b+MOD)%MOD; }

int getD(int n, int i, int j);

int getA(int n, int i, int j) { // what about getA(n,0,j)?
    if (i == j || i < 0 || i > n-1 || j < 0 || j > n-1) return 0;
    if (i == 0) {
        if (aa[n][j]) return AA[n][j];
        aa[n][j] = 1;
        if (j == 1) {
            if (n == 2) AA[n][j] = 1;
            else if (n % 2 == 0) AA[n][j] = 0;
            else {
                FOR(i,1,n-1) AA[n][j] = ad(AA[n][j],getA(n-1,0,i));
            }
        } else {
            if (n % 2 == 1) AA[n][j] = sub(getA(n,0,j-1),getA(n-1,0,j-1));
            else AA[n][j] = ad(getA(n,0,j-1),getA(n-1,0,j-1));
        }
        // cout << "A " << n << " " << i << " " << j << " " << AA[n][j] << "\n";
        return AA[n][j];
    }
    if (a[i][j]) return A[i][j];
    
    a[i][j] = 1;
    A[i][j] = sub(getA(n,i-1,j),getD(n-1,i-1,j-1));
    // cout << "A " << n << " " << i << " " << j << " " << A[i][j] << " " << getA(n,i-1,j) << " " <<  getD(n-1,i-1,j-1) << "\n";
    return A[i][j];
}

int getD(int n, int i, int j) { 
    if (i == j || i <= 0 || i > n-1 || j < 0 || j > n-1) return 0;
    if (d[i][j]) return D[i][j];
    d[i][j] = 1;
    D[i][j] = ad(getD(n,i-1,j),getA(n-1,i-1,j-1));
    // cout << "D " << n << " " << i << " " << j << " " << D[i][j] << "\n";
    return D[i][j];
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> cs >> cf;
    if (cs > cf) swap(cs,cf);
    cs --, cf --;
    // cout << getA(N,cs,cf) << " " << getD(N,cs,cf) << "\n";
    cout << ad(getA(N,cs,cf),getD(N,cs,cf));
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

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