1845E - Boxes and Balls - CodeForces Solution

#include<bits/stdc++.h>
#pragma GCC  optimize("O3")
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pi pair<ll,ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define alll(x) ((x).begin()+1), (x).end()
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define mod mod
#define endl '\n'
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9+7;

void io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

template<class T>
bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

template<class T>
bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }

void nop() {
    cout << -1 << endl;
    return;
}

const int N = 1505 ;
int n , k ;
int dp[N][N] , new_dp[N][N] ;
ll a[N] ;
void add(int& x , int y)
{
    x += y ;
    if(x>=mod) x-= mod ;
//    return (x+y)%mod ;
}



void solve() {
    cin>>n>>k ;
    vector<int> v ;
    v.pb(0) ;
    for(int i = 1 ; i<=n ; i++){
        cin>>a[i] ;
        if(a[i]) v.pb(i) ;
    }
    int m = v.size() ;
    --m ;



    dp[0][0] = 1 ;
    for(int i = 1 ; i<=n ; i++){
        for(int j = m ; j ; j--){
            int d = abs(i - v[j]) ;
            for(int moves = 0 ; moves + d <= k ; moves++){
                add(dp[j][moves+d] , dp[j-1][moves]) ;
            }
        }

    }
    int ans = 0 ;
    for(int x = k ; x>=0 ; x-=2)  add(ans , dp[m][x]) ;

    cout<<ans<<endl;


//    cout<<work(1 , 0 , 0)<<endl;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif
    io();
    ll tt = 1;
//    cin>>tt ;
    while (tt--) {
        solve();
    }

    return 0;
}