제출 #204195

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
204195		amoo_safar	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	121 ms	16360 KiB

skyscraper

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 1e2 + 10;
const int L = 1e3 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

int n, l, a[N], ps[N];
int mul(int a, int b){
	return (1ll * a * b) % Mod;
}
int mn[N][L][2][2];
int dp[N][N][L][2][2];

int Get(int l, int r){
	return ps[max(0, r)] - ps[max(0, l)];
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> l;
	if(n == 1) return cout << "1\n", 0;

	for(int i = 0; i < n; i++) cin >> a[i];
	sort(a, a + n);
	for(int i = 1; i <= n; i++) ps[i] = ps[i - 1] + a[i - 1];
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= i; j++){
			int p = n - i;
			mn[i][j][0][0] = 2 * Get(p - (j-1), p) + Get(p - (j+1), p - (j-1));
			mn[i][j][0][1] = 2 * Get(p - (j-1), p) + Get(p - j, p - (j-1));
			mn[i][j][1][0] = 2 * Get(p - (j-1), p) + Get(p - j, p - (j-1));
			mn[i][j][1][1] = 2 * Get(p - (j-1), p);	
		}
	}
	reverse(a, a + n);
	dp[1][1][ 2*a[0] - mn[1][1][0][0] ][0][0] = 1;
	dp[1][1][ a[0] - mn[1][1][1][0] ][1][0] = 1;
	dp[1][1][ a[0] - mn[1][1][0][1] ][0][1] = 1;
	
	int C, nC, X, P;
	for(int i = 1; i < n; i++){
		X = a[i];
		for(int j = 1; j <= i; j++){
			for(int c = 0; c <= l; c++){
				for(int b1 = 0; b1 < 2; b1++){ for(int b2 = 0; b2 < 2; b2++){
					if(!dp[i][j][c][b1][b2]) continue;
					C = c + mn[i][j][b1][b2];
					if(!b1){
						nC = C + X - mn[i + 1][j + 1][1][b2];
						if(0 <= nC && nC <= l)
							(dp[i + 1][j + 1][nC][1][b2] += dp[i][j][c][b1][b2]) %= Mod;
						
						nC = C - X - mn[i + 1][j][1][b2];
						if(0 <= nC && nC <= l)
							(dp[i + 1][j][nC][1][b2] += dp[i][j][c][b1][b2]) %= Mod;
					}
					if(!b2){
						nC = C + X - mn[i + 1][j + 1][b1][1];
						if(0 <= nC && nC <= l)
							(dp[i + 1][j + 1][nC][b1][1] += dp[i][j][c][b1][b2]) %= Mod;
						
						nC = C - X - mn[i + 1][j][b1][1];
						if(0 <= nC && nC <= l)
							(dp[i + 1][j][nC][b1][1] += dp[i][j][c][b1][b2]) %= Mod;
					}

					P = 2 * j - b1 - b2;
					nC = C - mn[i + 1][j][b1][b2];
					if(0 <= nC && nC <= l)
						(dp[i + 1][j][nC][b1][b2] += mul(P, dp[i][j][c][b1][b2]) ) %= Mod;
					
					P = j + 1 - b1 - b2;
					nC = C + 2*X - mn[i + 1][j + 1][b1][b2];
					if(0 <= nC && nC <= l)
						(dp[i + 1][j + 1][nC][b1][b2] += mul(P, dp[i][j][c][b1][b2]) ) %= Mod;

					P = j - 1;
					nC = C - 2*X - mn[i + 1][j - 1][b1][b2];
					if(0 <= nC && nC <= l)
						(dp[i + 1][j - 1][nC][b1][b2] += mul(P, dp[i][j][c][b1][b2]) ) %= Mod;
				}
				}
			}
		}
	}

	int ans = 0;
	for(int i = 0; i <= l; i++){
		ans = (ans + dp[n][1][i][1][1]) % Mod;
	}
	cout << ans << '\n';
	return 0;
}

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