Submission #492246

#	Time	Username	Problem	Language	Result	Execution time	Memory
492246		inluminas	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	214 ms	197444 KiB

skyscraper

#include"bits/stdc++.h"
using namespace std;

#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX

const ll mod=1e9+7;
ll dp[120][120][1020][5];

int main(){
  fastio;

  int n,L;
  cin>>n>>L;
  int a[n+1];
  for(int i=1;i<=n;i++) cin>>a[i];
  sort(a+1,a+n+1);

  for(int open=0;open<=2;open++){
    dp[1][1][0][open]=1+(open==1);
  }

  for(int i=1;i<n;i++){
    int d=a[i+1]-a[i];
    for(int j=1;j<=n;j++){
      for(int cost=0;cost<=L;cost++){
        for(int close=0;close<=2;close++){
          int nxt=cost+(j+j-close)*d;
          if(nxt<=L){
            dp[i+1][j+1][nxt][close]+=dp[i][j][cost][close]*(j+1-close);
            dp[i+1][j+1][nxt][close]%=mod;


            dp[i+1][j][nxt][close]+=dp[i][j][cost][close]*(j+j-close);
            dp[i+1][j][nxt][close]%=mod;
          }

          if(nxt<=L && j-1>0){
            dp[i+1][j-1][nxt][close]+=dp[i][j][cost][close]*(j-1);
            dp[i+1][j-1][nxt][close]%=mod;
          }

          if(nxt<=L && close+1<=2){
            dp[i+1][j][nxt][close+1]+=dp[i][j][cost][close]*(2-close);
            dp[i+1][j][nxt][close+1]%=mod;

            dp[i+1][j+1][nxt][close+1]+=dp[i][j][cost][close]*(2-close);
            dp[i+1][j+1][nxt][close+1]%=mod;
          }
        }
      }
    }
  }
  ll ans=0;
  for(int cost=0;cost<=L;cost++){
    ans+=dp[n][1][cost][2];
    ans%=mod;
  }
  cout<<ans<<endl;
  return 0;
}

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