Submission #501192

#	Time	Username	Problem	Language	Result	Execution time	Memory
501192		radal	Kangaroo (CEOI16_kangaroo)	C++14	51 / 100	2064 ms	23072 KiB

kangaroo

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
const long long int N = 2e3+20,mod = 1e9+7,inf = 1e18+10,sq = 32000;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
inline int poww(int n,int k){
    int c = 1;
    while (k){
        if (k&1) c = (1ll*c*n)%mod;
        n = (1ll*n*n)%mod;
        k >>= 1;
    }
    return c;
}
int dp[2][N][N][2],pre[2][N][N][2];
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    int n,s,f;
    cin >> n >> s >> f;
    if (s > f) swap(s,f);
    if ((n&1) && n > 1000 && f-s < 1000){
        f = f-s+1;
        s = 1;
    }
    swap(f,s);
    dp[1][1][1][0] = 1;
    dp[1][1][1][1] = 1;
    pre[1][1][1][1] = 1;
    pre[1][1][1][0] = 1;
    rep(i,2,n+1){
        int d = (i&1);
        int r = min(i,f);
        rep(j,1,r+1){
            rep(k,1,i+1){
                if (j == k){
                    dp[d][j][k][0] = 0;
                    dp[d][j][k][1] = 0;
                    pre[d][j][k][0] = pre[d][j][k-1][0];
                    pre[d][j][k][1] = pre[d][j][k-1][1];
                    continue;
                }
                if (j > k){
                    dp[d][j][k][0] = pre[1-d][j-1][k-1][1];
                    dp[d][j][k][1] = mkay(pre[1-d][j-1][i-1][0],-pre[1-d][j-1][k-1][0]);
                }
                else{
                    dp[d][j][k][0] = pre[1-d][j][k-1][1];
                    dp[d][j][k][1] = mkay(pre[1-d][j][i-1][0],-pre[1-d][j][k-1][0]);
                }
                pre[d][j][k][0] = mkay(pre[d][j][k-1][0],dp[d][j][k][0]);
                pre[d][j][k][1] = mkay(pre[d][j][k-1][1],dp[d][j][k][1]);
            }
        }
    }
    int d = (n&1);
    cout << mkay(dp[d][f][s][0],dp[d][f][s][1]);
}

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