제출 #741118

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
741118		Mihailo	Skyscraper (JOI16_skyscraper)	C++17	0 / 100	2 ms	1876 KiB

skyscraper

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

long long N, L, a[200], dp[150][150][1200][5], x;

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>N>>L;
    for(int i=1; i<=N; i++) cin>>a[i];
    sort(a+1, a+N+1);
    dp[0][0][0][0]=1;
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=N; j++) {
            for(int s=0; s<=L; s++) {
                x=2*j*(a[i+1]-a[i]);
                if(s-x>=0) {
                    dp[i][j][s][0]+=j*dp[i-1][j-1][s-x][0]+2*j*dp[i-1][j][s-x][0]+j*dp[i-1][j+1][s-x][0];
                }
                x=(2*j-1)*(a[i+1]-a[i]);
                if(s-x>=0) {
                    dp[i][j][s][1]+=(j-1)*dp[i-1][j-1][s-x][1]+(2*j-1)*dp[i-1][j][s-x][1]+j*dp[i-1][j+1][s-x][1];
                    dp[i][j][s][1]+=2*dp[i-1][j-1][s-x][0]+2*dp[i-1][j][s-x][0];
                }
                x=(2*j-2)*(a[i+1]-a[i]);
                if(s-x>=0) {
                    dp[i][j][s][2]+=max(0, (j-2))*dp[i-1][j-1][s-x][2]+(2*j-2)*dp[i-1][j][s-x][2]+j*dp[i-1][j+1][s-x][2];
                    dp[i][j][s][2]+=dp[i-1][j-1][s-x][1]+dp[i-1][j][s-x][1];
                }
                for(int k=0; k<=2; k++) dp[i][j][s][k]%=MOD;
            }
        }
    }
    long long rez=0;
    for(int i=0; i<=L; i++) rez+=dp[N][1][i][2];
    cout<<rez;
    return 0;
}

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