oj.uz

Submission #1079336

# Submission time Handle Problem Language Result Execution time Memory
1079336 2024-08-28T13:13:25 Z alexander707070 JOIRIS (JOI16_joiris) C++14
0 / 100
 1000 ms 11612 KB 
#include<bits/stdc++.h>
#define MAXN 107
#define MAXS 5007
using namespace std;

const long long mod=1e9+7;

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

unordered_map<int,long long> dp[MAXN][MAXN][3][3];
unordered_map<int,long long> dp2[MAXN][MAXN][3][3];

long long even(int pos,int bal,int sum,int l,int r){
    if(bal<0 or bal>n)return 0;

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

    if(pos==n+1 and bal==n/2 and l+r==3 and sum<=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][l][r].find(sum)!=dp[pos][bal][l][r].end())return dp[pos][bal][l][r][sum];
    long long curr=0;

    curr+=even(pos+1,bal,sum,l,r)*free;

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

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

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

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

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

    return curr;
}


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

    if(pos==n+1 and (bal==n/2-1 or bal==n/2+1) and l==r and l!=0 and sum<=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][l][r].find(sum)!=dp2[pos][bal][l][r].end())return dp2[pos][bal][l][r][sum];
    long long curr=0;

    curr+=odd(pos+1,bal,sum,l,r)*free;

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

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

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

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

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

void calc_even(){
    ans+=even(1,n/2,0,0,0);
}

void calc_odd(){
    ans+=odd(1,n/2,0,0,0);
}

int br;

void check(){
    int res=0;
    for(int i=2;i<=n;i++){
        res+=abs(a[i-1]-a[i]);
    }

    if(res<=s)br++;
}

void brute(){
    do{
        check();
    }while(next_permutation(a+1,a+n+1));
}

int main(){

    cin>>n>>s;

    int mins=1000;

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

    for(int i=1;i<=n;i++){
        a[i]-=mins;
    }

    sort(a+1,a+n+1);

    /*calc_even();
    calc_odd();

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

    brute();
    cout<<br<<"\n";

    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1004 ms 11608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1004 ms 11608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1004 ms 11608 KB Time limit exceeded
2 Halted 0 ms 0 KB -