oj.uz

답안 #208661

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
208661 2020-03-12T01:34:53 Z bensonlzl Skyscraper (JOI16_skyscraper) C++14
15 / 100
 155 ms 260720 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll dp[105][105][1005][3];

ll N, L, A[105], D[105];

const ll mod = 1000000007;

ll calc(int n, int c, int l, int edge){
	if (l < 0) return 0;
	if (n == N) return ((c >= 1) && (c <= 2) && (c == edge));
	if (dp[n][c][l][edge] != -1) return dp[n][c][l][edge];
	ll ans = 0;
	if (edge < 2){
		// Add to one end of the array	
		ans += calc(n+1,c+1,l - (2 * (c+1) - edge - 1) * D[n],edge+1) * (2-edge);

		
		if (2*c - edge - 1 > 0) ans += calc(n+1,c,l - (2*c - edge - 1) * D[n],edge+1) * (2-edge);
	}
	// Add new segment
	if (c + 1 - edge > 0) ans += calc(n+1,c+1,l - (2*(c+1) - edge) * D[n], edge) * (c + 1 - edge);
	
	// Merge 2 existing segments
	if (c > 0) ans += calc(n+1,c-1,l - (2*(c-1) - edge) * D[n], edge) * (c-1);
	
	// Add to an existing segment
	if (2*c > edge) ans += calc(n+1,c,l - (2*c - edge) * D[n], edge) * (2 * c - edge);
	ans %= mod;
	return dp[n][c][l][edge] = ans;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	memset(dp,-1,sizeof(dp));
	cin >> N >> L;
	for (int i = 1; i <= N; ++i){
		cin >> A[i];
	}
	sort(A+1,A+N+1);
	for (int i = 1; i <= N; ++i){
		D[i] = A[i+1] - A[i];
	}
	cout << calc(1,0,L,0) << '\n';
}

Subtask #1
0 / 5.0

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

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 260500 KB Output is correct
2 Correct 138 ms 260472 KB Output is correct
3 Correct 138 ms 260472 KB Output is correct
4 Correct 147 ms 260720 KB Output is correct
5 Correct 148 ms 260472 KB Output is correct
6 Correct 142 ms 260472 KB Output is correct
7 Correct 138 ms 260476 KB Output is correct
8 Correct 143 ms 260492 KB Output is correct
9 Correct 139 ms 260472 KB Output is correct
10 Correct 137 ms 260472 KB Output is correct

Subtask #3
0 / 80.0

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