Submission #1079316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079316		alexander707070	Skyscraper (JOI16_skyscraper)	C++14	15 / 100	567 ms	6736 KiB

skyscraper

#include<bits/stdc++.h>
#define MAXN 107
#define MAXS 2007
using namespace std;

const long long mod=1e9+7;

int n,s,a[MAXN],ans;

long long dp[MAXN][MAXN/2+5][MAXS][3][3];
long long dp2[MAXN][MAXN/2+5][MAXS][3][3];

long long even(int pos,int bal,int sum,int l,int r){

    long long free=2*(bal-5)+(-(l==1)-(r==1)) - (-(l==2)-(r==2));
    if(free<0)return 0;

    if(pos==n+1 and bal==5 and l+r==3 and sum-1000<=s and free==0){
        return 1;
    }else if(pos==n+1)return 0;

    if(free==0 and pos!=1)return 0;


    if(dp[pos][bal][sum][l][r]>0)return dp[pos][bal][sum][l][r];

    dp[pos][bal][sum][l][r]+=even(pos+1,bal,sum,l,r)*free;

    if(l==0){
        if(r!=1)dp[pos][bal][sum][l][r]+=even(pos+1,bal+1,sum-a[pos],1,r);
        if(r!=2)dp[pos][bal][sum][l][r]+=even(pos+1,bal-1,sum+a[pos],2,r);
    }

    if(r==0){
        if(l!=1)dp[pos][bal][sum][l][r]+=even(pos+1,bal+1,sum-a[pos],l,1);
        if(l!=2)dp[pos][bal][sum][l][r]+=even(pos+1,bal-1,sum+a[pos],l,2);
    }

    long long mult=bal-5+1-(l==1)-(r==1);
    long long mult2=bal-5-1+(l==2)+(r==2);

    dp[pos][bal][sum][l][r]+=even(pos+1,bal+1,sum-2*a[pos],l,r)*mult;
    dp[pos][bal][sum][l][r]+=even(pos+1,bal-1,sum+2*a[pos],l,r)*mult2;

    dp[pos][bal][sum][l][r]%=mod;

    return dp[pos][bal][sum][l][r];
}


long long odd(int pos,int bal,int sum,int l,int r){
    
    long long free=2*(bal-5)+(-(l==1)-(r==1)) - (-(l==2)-(r==2));
    if(free<0)return 0;

    if(pos==n+1 and (bal==4 or bal==6) and l==r and l!=0 and sum-1000<=s and free==0){
        return 1;
    }else if(pos==n+1)return 0;

    if(free==0 and pos!=1)return 0;

    if(dp2[pos][bal][sum][l][r]>0)return dp2[pos][bal][sum][l][r];

    dp2[pos][bal][sum][l][r]+=odd(pos+1,bal,sum,l,r)*free;

    if(l==0){
        if(r!=2)dp2[pos][bal][sum][l][r]+=odd(pos+1,bal+1,sum-a[pos],1,r);
        if(r!=1)dp2[pos][bal][sum][l][r]+=odd(pos+1,bal-1,sum+a[pos],2,r);
    }

    if(r==0){
        if(l!=2)dp2[pos][bal][sum][l][r]+=odd(pos+1,bal+1,sum-a[pos],l,1);
        if(l!=1)dp2[pos][bal][sum][l][r]+=odd(pos+1,bal-1,sum+a[pos],l,2);
    }

    long long mult=bal-5+1-(l==1)-(r==1);
    long long mult2=bal-5-1+(l==2)+(r==2);

    dp2[pos][bal][sum][l][r]+=odd(pos+1,bal+1,sum-2*a[pos],l,r)*mult;
    dp2[pos][bal][sum][l][r]+=odd(pos+1,bal-1,sum+2*a[pos],l,r)*mult2;

    dp2[pos][bal][sum][l][r]%=mod;
    
    return dp2[pos][bal][sum][l][r];
}

void calc_even(){
    ans+=even(1,5,1000,0,0);
}

void calc_odd(){
    ans+=odd(1,5,1000,0,0);
}

int main(){

    cin>>n>>s;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);

    calc_even();
    calc_odd();

    cout<<ans%mod<<"\n";

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 80