제출 #333759

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
333759		nextgenxing	Skyscraper (JOI16_skyscraper)	C++14	20 / 100	87 ms	25452 KiB

skyscraper

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

typedef long long ll;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define F0R(i, x) FOR(i, 0, x)
const int MAX_N = 102;
const int MAX_L = 1002;
const ll MOD = 1000000007;

ll ad(ll& a, ll b, ll mod = MOD){
    a = a+b; if(a >= mod) a -= mod;
    return a;
}

int n, l;
ll dp[MAX_N][MAX_N][MAX_L][3], a[MAX_N];

int main(int argc, const char * argv[]) {
    cin >> n >> l; F0R(i, n) cin >> a[i];
    sort(a, a+n), a[n] = 10001;
    if(n == 1){ cout << 1 << endl; return 0; }
    if(a[1]-a[0] <= l) dp[1][1][a[1]-a[0]][1] = 2;
    if(2*(a[1]-a[0]) <= l) dp[1][1][2*(a[1]-a[0])][0] = 1;
    FOR(i, 1, n) FOR(j, 1, i+1) F0R(k, l+1) F0R(z, 3) if(dp[i][j][k][z]){
        int d = a[i+1]-a[i];
        if(z < 2 && k+d*(2*j-z-1) <= l) ad(dp[i+1][j][k+d*(2*j-z-1)][z+1], (2-z)*dp[i][j][k][z]);
        if(z < 2 && k+d*(2*j-z+1) <= l) ad(dp[i+1][j+1][k+d*(2*j-z+1)][z+1], (2-z)*dp[i][j][k][z]);
        if(k+d*(2*j-z) <= l) ad(dp[i+1][j][k+d*(2*j-z)][z], (2*j-z)*dp[i][j][k][z]);
        if(k+d*(2*j-z+2) <= l) ad(dp[i+1][j+1][k+d*(2*j-z+2)][z], (j-z+1)*dp[i][j][k][z]);
        if(j && k+d*(2*j-z-2) <= l) ad(dp[i+1][j-1][k+d*(2*j-z-2)][z], (j-1)*dp[i][j][k][z]);
    }
    ll ans = 0; F0R(i, l+1) ad(ans, dp[n][1][i][2]);
    cout << ans << endl;
    return 0;
}

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