Submission #1031517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031517		vjudge1	Skyscraper (JOI16_skyscraper)	C++17	20 / 100	138 ms	179028 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
//int dp0[101][51],dp1[105][51],dp2[101][51];
long long cnt1[1<<14][14][101],cnt2[1<<8][8][1010];
int vl[14],mod=1e9+7;
int main(){
    int n,l;
    cin>>n>>l;
    if(n>8){
        for(int i=0;i<n;i++)
            cin>>vl[i],cnt1[1<<i][i][0]=1;
        for(int i=1;i<1<<n;i++)
            for(int j=0;j<n;j++)if(i&1<<j) {
                for(int k=0;k<=l;k++)
                    cnt1[i][j][k]%=mod;
                for(int k=0;k<n;k++)if(~i&1<<k){
                    int cst=abs(vl[j]-vl[k]);
                    for(int v=0;v<=l-cst;v++)
                        cnt1[i^1<<k][k][v+cst]+=cnt1[i][j][v];
                }
            }
        long long ans=0;
        for(int i=0;i<=l;i++)
            for(int x=0;x<n;x++)
                ans+=cnt1[(1<<n)-1][x][i];
        cout<<ans%mod;
    } else {
        for(int i=0;i<n;i++)
            cin>>vl[i],cnt2[1<<i][i][0]=1;
        for(int i=1;i<1<<n;i++)
            for(int j=0;j<n;j++)if(i&1<<j) {
                for(int k=0;k<=l;k++)
                    cnt2[i][j][k]%=mod;
                for(int k=0;k<n;k++)if(~i&1<<k){
                    int cst=abs(vl[j]-vl[k]);
                    for(int v=0;v<=l-cst;v++)
                        cnt2[i^1<<k][k][v+cst]+=cnt2[i][j][v];
                }
            }
        long long ans=0;
        for(int i=0;i<=l;i++)
            for(int x=0;x<n;x++)
                ans+=cnt2[(1<<n)-1][x][i];

        cout<<ans%mod;
    }
}

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