Submission #772189

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
772189	2023-07-03 17:50:13	ttamx	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	178 ms	105392 KiB

skyscraper

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105;
const int M=1005;
const int mod=1e9+7;
int n,l;
int a[N];
ll dp[N][N][M][4];
ll ans;
int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> l;
    for(int i=1;i<=n;i++)cin >> a[i];
    if(n==1)cout << 1,exit(0);
    sort(a+1,a+n+1);
    dp[1][1][0][0]=1;
    dp[1][1][0][1]=2;
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++){
            for(int k=0;k<=l;k++){
                for(int e=0;e<3;e++){
                    int res=k+(a[i]-a[i-1])*(2*j-e);
                    if(res>l)continue;
                    dp[i][j-1][res][e]+=dp[i-1][j][k][e]*(j-1)%mod;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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