Submission #799628

#	Time	Username	Problem	Language	Result	Execution time	Memory
799628		manizare	Skyscraper (JOI16_skyscraper)	C++14	15 / 100	3 ms	2900 KiB

skyscraper

#include <bits/stdc++.h>  
#define pii pair <int,int>  
#define F first  
#define S second  
#define all(a) a.begin(),a.end()  
#define pb push_back 
#define int long long 
using namespace std ;

const int maxn = 102 , inf  = 1e18 , mod = 1e9 + 7 ;  
int dp[3][102][102][1002] , a[102] ; 
signed main(){ 
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) ;
  int n , l ;cin >> n >> l ;
  for(int i = 1 ; i <= n; i++){
    cin >> a[i] ; 
  }
  sort(a+1 , a+1+n) ; 
  dp[0][1][1][0] = 1 ; 
  dp[1][1][1][0] = 2; 
  for(int z =0 ;  z< 3 ; z++){
    for(int i = 2; i <= n; i ++){
      int d = a[i] - a[i-1] ; 
      for(int j = 1 ; j <= n ; j++){
        for(int k = 0 ; k <= l ; k++){
          if(k-(2*(j+1)-z)*d >= 0)dp[z][i][j][k] += (dp[z][i-1][j+1][k-(2*(j+1)-z)*d] * j %mod) ;    
          if(k-d*(2*j - z) >= 0 )dp[z][i][j][k] += (dp[z][i-1][j][k-d*(2*j - z)] *(2*j-z) % mod) ;
          if(k-(2*(j-1)-z)*d >= 0)dp[z][i][j][k] += (dp[z][i-1][j-1][k-(2*(j-1)-z)*d] *(j - z) %mod) ;
          if(z!=0){
            if(k-(2*j-(z-1))*d >= 0 ) dp[z][i][j][k] += (dp[z-1][i-1][j][k-(2*j-(z-1))*d] * (3-z) % mod) ; 
            if(k-d*(2*j-2-(z-1)) >= 0)dp[z][i][j][k] += (dp[z-1][i-1][j-1][k-d*(2*j-2-(z-1))] * (3-z) % mod) ;
          }
          dp[z][i][j][k] %= mod ;
        }
      }
    }
  }
  int ans =0 ; 
  for(int i =0 ; i <= l ; i++){
    ans = (ans + dp[2][n][1][i])%mod ;
  }
  cout << ans ; 
} 
/* 
 
*/

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