oj.uz

Submission #799621

# Submission time Handle Problem Language Result Execution time Memory
799621 2023-07-31T16:47:13 Z manizare Skyscraper (JOI16_skyscraper) C++14
15 / 100
 3 ms 3028 KB 
#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][maxn][maxn][maxn*11] , a[maxn] ; 
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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2132 KB Output is correct
2 Correct 2 ms 2900 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2900 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 2 ms 2900 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 3 ms 2900 KB Output is correct
10 Correct 2 ms 2900 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -