oj.uz

Submission #1079341

# Submission time Handle Problem Language Result Execution time Memory
1079341 2024-08-28T13:14:41 Z alexander707070 Skyscraper (JOI16_skyscraper) C++14
20 / 100
 2000 ms 287880 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;

    if(n==1){
        cout<<1<<"\n";
        return 0;
    }

    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";

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11612 KB Output is correct
2 Correct 7 ms 11612 KB Output is correct
3 Correct 7 ms 11608 KB Output is correct
4 Correct 8 ms 11608 KB Output is correct
5 Correct 7 ms 12124 KB Output is correct
6 Correct 7 ms 12124 KB Output is correct
7 Correct 9 ms 12124 KB Output is correct
8 Correct 6 ms 11896 KB Output is correct
9 Correct 7 ms 12136 KB Output is correct
10 Correct 5 ms 11868 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12376 KB Output is correct
2 Correct 46 ms 20164 KB Output is correct
3 Correct 12 ms 13404 KB Output is correct
4 Correct 46 ms 20452 KB Output is correct
5 Correct 54 ms 21840 KB Output is correct
6 Correct 35 ms 17344 KB Output is correct
7 Correct 18 ms 14988 KB Output is correct
8 Correct 11 ms 13400 KB Output is correct
9 Correct 11 ms 13696 KB Output is correct
10 Correct 35 ms 18516 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11612 KB Output is correct
2 Correct 7 ms 11612 KB Output is correct
3 Correct 7 ms 11608 KB Output is correct
4 Correct 8 ms 11608 KB Output is correct
5 Correct 7 ms 12124 KB Output is correct
6 Correct 7 ms 12124 KB Output is correct
7 Correct 9 ms 12124 KB Output is correct
8 Correct 6 ms 11896 KB Output is correct
9 Correct 7 ms 12136 KB Output is correct
10 Correct 5 ms 11868 KB Output is correct
11 Correct 8 ms 12376 KB Output is correct
12 Correct 46 ms 20164 KB Output is correct
13 Correct 12 ms 13404 KB Output is correct
14 Correct 46 ms 20452 KB Output is correct
15 Correct 54 ms 21840 KB Output is correct
16 Correct 35 ms 17344 KB Output is correct
17 Correct 18 ms 14988 KB Output is correct
18 Correct 11 ms 13400 KB Output is correct
19 Correct 11 ms 13696 KB Output is correct
20 Correct 35 ms 18516 KB Output is correct
21 Correct 957 ms 135556 KB Output is correct
22 Execution timed out 2039 ms 287880 KB Time limit exceeded
23 Halted 0 ms 0 KB -