oj.uz

답안 #26103

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26103 2017-06-28T02:45:04 Z gabrielsimoes Skyscraper (JOI16_skyscraper) C++14
0 / 100
 0 ms 246512 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 102;
const int MAXL = 1002;
const ll MOD = 1e9+7;

#define upd(x, a) ((x) = ((x) + (a)) % MOD)

int N, L;
vector<int> v;
ll dp[MAXN][MAXN][3][MAXL];

int main()
{
	ios_base::sync_with_stdio(0);
	cin >> N >> L;

	v.resize(N+1);
	for (int i = 0; i < N; i++) cin >> v[i];
	sort(v.begin(), v.end());

	if (N == 1) return cout << 1 << endl, 0;

	v[N] = MAXL*100;
	if (v[1] - v[0] <= L) dp[1][1][1][v[1]-v[0]] = 2;
	if (2*(v[1] - v[0]) <= L) dp[1][1][0][2*(v[1]-v[0])] = 1;

	int nsum; ll cur;
	for (int i = 1; i <= N; i++) {
		int dif = v[i+1] - v[i];
		for (int cnt = 1; cnt <= i; cnt++) {
			for (int end = 0; end < 3; end++) {
				for (int sum = 0; sum <= L; sum++) {
					cur = dp[i][cnt][end][sum];
					if (cur == 0) continue;

					// try to fill the ends
					nsum = sum + dif*(2*cnt - end - 1);
					if (end < 2 && nsum <= L) {
						// no new component is created
						if (i == N-1) upd(dp[i+1][cnt][end+1][nsum], cur);
						else if (end == 0 || cnt > 1) upd(dp[i+1][cnt][end+1][nsum], ll(2-end)*ll(cnt-end)*cur);

						// a new component is created
						nsum += 2*dif;
						if (nsum <= L) upd(dp[i+1][cnt+1][end+1][nsum], ll(2-end)*cur);
					}

					// try to create a new component
					nsum = sum + dif*(2*cnt - end) + 2*dif;
					if (nsum <= L) upd(dp[i+1][cnt+1][end][nsum], cur);

					// try append to a component
					nsum = sum + dif*(2*cnt - end);
					if (nsum <= L) upd(dp[i+1][cnt][end][nsum], ll(2*cnt-end)*cur);

					// join two components together
					nsum = sum + dif*(2*cnt - end) - 2*dif;
					if (nsum <= L && cnt >= 2 && (i == N-1 || cnt > 2 || end < 2)) {
						if (end == 0) upd(dp[i+1][cnt-1][end][nsum], ll(cnt)*ll(cnt-1)*cur);
						else if (end == 1) upd(dp[i+1][cnt-1][end][nsum], ll(cnt-1)*ll(cnt-1)*cur);
						else if (end == 2) {
							if (i == N-1) upd(dp[i+1][cnt-1][end][nsum], cur);
							else upd(dp[i+1][cnt-1][end][nsum], ll(cnt-2)*ll(cnt-1)*cur);
						}
					}
				}
			}
		}
	}

	ll ans = 0;
	for (int i = 0; i <= L; i++)
		upd(ans, dp[N][1][2][i]);
	cout << ans << endl;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 246512 KB Output is correct
2 Correct 0 ms 246512 KB Output is correct
3 Incorrect 0 ms 246512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 246512 KB Output is correct
2 Incorrect 0 ms 246512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 246512 KB Output is correct
2 Correct 0 ms 246512 KB Output is correct
3 Incorrect 0 ms 246512 KB Output isn't correct
4 Halted 0 ms 0 KB -