제출 #81773

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
81773		Bodo171	Skyscraper (JOI16_skyscraper)	C++14	15 / 100	7 ms	1308 KiB

skyscraper

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int nmax=105;
const long long mod=1000*1000*1000+7;
long long dp[2][nmax][nmax*10][2][2];
int a[nmax];
int n,l,use,cost,newcost,st,dr;
long long i,gaps,difs,endss;
long long ans;
void prp(long long &a,long long b)
{
    a+=(b%mod);
    if(a>=mod)
        a-=mod;
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n>>l;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    //dp[use][cc][cost][fix_st][fix_dr]
    for(st=0;st<2;st++)
        for(dr=0;dr<2;dr++)
           dp[1][1][0][st][dr]=1;
    for(int cnt=2;cnt<=n;cnt++)
    {
        use=1-use;
        for(i=1;i<=n;i++)
          for(cost=0;cost<=l;cost++)
            for(st=0;st<2;st++)
              for(dr=0;dr<2;dr++)
               dp[1-use][i][cost][st][dr]=0;
        for(i=1;i<=n;i++)
          for(cost=0;cost<=l;cost++)
            for(st=0;st<2;st++)
              for(dr=0;dr<2;dr++)
        {
             gaps=i+1-st-dr;
             endss=2*(i-1)+(1-st)+(1-dr);
             newcost=(a[cnt]-a[cnt-1])*endss+cost;
             if(cost<=l)
             {
                 prp(dp[1-use][i-1][newcost][st][dr],1LL*dp[use][i][cost][st][dr]*(i-1));
                 prp(dp[1-use][i+1][newcost][st][dr],1LL*dp[use][i][cost][st][dr]*gaps);
                 prp(dp[1-use][i][newcost][st][dr],1LL*dp[use][i][cost][st][dr]*endss);
                 if(!st)
                 {
                     prp(dp[1-use][i+1][newcost][1][dr],dp[use][i][cost][st][dr]);
                     prp(dp[1-use][i][newcost][1][dr],dp[use][i][cost][st][dr]);
                 }
                 if(!dr)
                 {
                     prp(dp[1-use][i+1][newcost][st][1],dp[use][i][cost][st][dr]);
                     prp(dp[1-use][i][newcost][st][1],dp[use][i][cost][st][dr]);
                 }
             }
        }
    }
    use=1-use;
    for(i=0;i<=l;i++)
        prp(ans,dp[use][1][i][1][1]);
    cout<<ans;
    return 0;
}

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