oj.uz

Submission #492246

# Submission time Handle Problem Language Result Execution time Memory
492246 2021-12-06T07:32:33 Z inluminas Skyscraper (JOI16_skyscraper) C++14
100 / 100
 214 ms 197444 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 700 KB Output is correct
9 Correct 2 ms 1740 KB Output is correct
10 Correct 1 ms 716 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1228 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 1356 KB Output is correct
4 Correct 1 ms 1228 KB Output is correct
5 Correct 1 ms 1228 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 1 ms 972 KB Output is correct
8 Correct 1 ms 1356 KB Output is correct
9 Correct 1 ms 1484 KB Output is correct
10 Correct 1 ms 1228 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 700 KB Output is correct
9 Correct 2 ms 1740 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 1 ms 1228 KB Output is correct
12 Correct 1 ms 1228 KB Output is correct
13 Correct 1 ms 1356 KB Output is correct
14 Correct 1 ms 1228 KB Output is correct
15 Correct 1 ms 1228 KB Output is correct
16 Correct 2 ms 1484 KB Output is correct
17 Correct 1 ms 972 KB Output is correct
18 Correct 1 ms 1356 KB Output is correct
19 Correct 1 ms 1484 KB Output is correct
20 Correct 1 ms 1228 KB Output is correct
21 Correct 3 ms 4428 KB Output is correct
22 Correct 212 ms 197444 KB Output is correct
23 Correct 209 ms 188132 KB Output is correct
24 Correct 199 ms 184772 KB Output is correct
25 Correct 214 ms 195340 KB Output is correct
26 Correct 195 ms 173096 KB Output is correct
27 Correct 94 ms 98076 KB Output is correct
28 Correct 112 ms 120008 KB Output is correct
29 Correct 191 ms 190540 KB Output is correct
30 Correct 212 ms 192632 KB Output is correct