Submission #966820

#	Time	Username	Problem	Language	Result	Execution time	Memory
966820		berr	Kangaroo (CEOI16_kangaroo)	C++17	51 / 100	2033 ms	63508 KiB

kangaroo

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

const int N = 2e3+5, mod=1e9+7;

vector<vector<array<int, 2>>> dp(N, vector<array<int, 2>>(N, array<int, 2>{0LL, 0LL}));
vector<vector<array<int, 2>>> dpn(N, vector<array<int, 2>>(N, array<int, 2>{0LL, 0LL}));

int calc(int n, int cs, int cf, int dir){
    if(cs==cf) return dpn[cs][cf][dir]=0;
    if(dpn[cs][cf][dir]!=-1) return dpn[cs][cf][dir];
    if(n==2 && (cs<cf)==dir) return dpn[cs][cf][dir]=1;
    if(n==2) return dpn[cs][cf][dir]=0;
    if(dir == 1 && cs==n-1) return dpn[cs][cf][dir]=0;
    else if(dir==0 && cs==0) return dpn[cs][cf][dir]=0;;

    int v=0, check=0, ans=0;
    if(dir==0){
        ans+=dp[cs-1][cf-(cs<cf)][1];
    }
    else{
        int v=cs;
        ans+=dp[v][cf-(cs<cf)][0];

 
    }
    return dpn[cs][cf][dir]=ans;
    
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
  /* freopen("kangaroo.in", "r", stdin);
    freopen("kangaroo.out", "w", stdout);
*/
    int n, cs, cf; cin >> n >> cs >> cf;
    cs--; cf--;


      
    for(int i=2; i<n; i++){
        for(int l=0; l<=i; l++){
            for(int j=0; j<=i; j++){
                for(int x=0; x<2; x++){
                    dpn[l][j][x] =-1;
                }
            }
        }
        for(int l=0; l<i; l++){
            for(int j=0; j<i; j++){
                for(int x=0; x<2; x++){
                    dpn[l][j][x] = calc(i, l, j, x);
                }
            }
        }

        for(int l=i-2; l>=0; l--){
            for(int j=0; j<i; j++){

                dpn[l][j][0]+=dpn[l+1][j][0];
                dpn[l][j][0] %= mod;
            }
        }

        for(int l=1; l<i; l++){
            for(int j=0; j<i; j++){
                dpn[l][j][1] += dpn[l-1][j][1];
                dpn[l][j][1] %= mod;
            }
        }

        swap(dpn, dp);

    }

    for(int l=0; l<=n; l++){
        for(int j=0; j<=n; j++){
            for(int x=0; x<2; x++){
                dpn[l][j][x] =-1;
            }
        }
    }
    cout<<((calc(n, cs, cf, 0)+calc(n, cs, cf, 1))%mod);
   // cout<<"tamam";
}

Compilation message (stderr)

kangaroo.cpp: In function 'int calc(int, int, int, int)':
kangaroo.cpp:20:9: warning: unused variable 'v' [-Wunused-variable]
   20 |     int v=0, check=0, ans=0;
      |         ^
kangaroo.cpp:20:14: warning: unused variable 'check' [-Wunused-variable]
   20 |     int v=0, check=0, ans=0;
      |              ^~~~~

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