Submission #953173

#	Time	Username	Problem	Language	Result	Execution time	Memory
953173		Deepesson	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	63 ms	77652 KiB

skyscraper

#include <bits/stdc++.h>
#define MAX 105
int tab[MAX][MAX][1005][3];
bool existe[MAX][MAX][1005][3];
using ll = long long;
ll MOD = 1e9+7;
std::vector<int> alturas;
ll N,L;
ll dp(ll cur,ll conjs,ll soma,ll bordas){
    if(soma>L)return 0;
    if(cur==N){
        if(conjs==1&&!bordas){
            return 1;
        }
        return 0;
    }
    if(existe[cur][conjs][soma][bordas])return tab[cur][conjs][soma][bordas];
    existe[cur][conjs][soma][bordas]=1;
    ll num_lados = 2*conjs-(2-bordas);
    ll custo=0;
    if(cur){
        custo=alturas[cur]-alturas[cur-1];
    }
    ll custo_adicional = custo*num_lados;
    ll cur1 = 0,cur2=0,cur3=0;
    ///Une dois caras
    if(conjs>1){
        int remove=0;
        if(bordas==1){
            remove=conjs-1;
        }else if(bordas==0){
            remove=2*conjs-3;///Cuidado com uniao q acaba
            if(conjs!=2)remove=2*conjs-2;
        }
        if(conjs!=2||bordas||(cur==N-1))
        cur1 = (((conjs)*(conjs-1)-(remove))*dp(cur+1,conjs-1,soma+custo_adicional,bordas)) % MOD;
    }
    ///Aumenta um cara
    if(conjs>=1){
        if(!bordas){///Jah escolheu ambas as bordas
            cur2 = ((conjs*2-2)*dp(cur+1,conjs,soma+custo_adicional,bordas)) % MOD;
        }else if(bordas==1){
            ///Nao marca borda
            cur2 = ((conjs*2-1)*dp(cur+1,conjs,soma+custo_adicional,bordas)) % MOD;
            ///Marca borda
            if(conjs>1){///Caso tenha mais de 2 caras
                cur2 += ((conjs-1)*dp(cur+1,conjs,soma+custo_adicional,bordas-1)) % MOD;
            }else if(cur==N-1&&conjs==1){///Caso seja o ultimo cara msm
                cur2 += (dp(cur+1,conjs,soma+custo_adicional,bordas-1)) % MOD;
            }
        }else {
            ///Nao marca borda
            cur2 = ((conjs*2)*dp(cur+1,conjs,soma+custo_adicional,bordas)) % MOD;
            ///Marca borda
            if(bordas)
            cur2 += ((2*conjs)*dp(cur+1,conjs,soma+custo_adicional,bordas-1)) % MOD;
        }
    }
    ///Cria um novo cara
    {
        ///Ele nao eh fronteira
        cur3 = dp(cur+1,conjs+1,soma+custo_adicional,bordas);
        ///Ele eh fronteira
        if(bordas)
            cur3 += (bordas)*dp(cur+1,conjs+1,soma+custo_adicional,bordas-1);
    }
    return tab[cur][conjs][soma][bordas] = (cur1+cur2+cur3)%MOD;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>N>>L;
    if(N==1){
        std::cout<<"1\n";
        return 0;
    }
    for(int i=0;i!=N;++i){
        int x;
        std::cin>>x;
        alturas.push_back(x);
    }
    std::sort(alturas.begin(),alturas.end());
    std::cout<<dp(0,0,0,2)<<"\n";
}

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