oj.uz

답안 #685057

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
685057 2023-01-23T08:26:35 Z NeroZein Skyscraper (JOI16_skyscraper) C++14
15 / 100
 1 ms 340 KB 
/*
 *    author: NeroZein
 *    created: 23.01.2023 11:07:10
*/
#include <bits/stdc++.h>
using namespace std;

const int md = 1e9+7; 

inline void add(int& a, int b) {
	a += b;
	if(a >= md){
		a -= md;
	}
}

inline int mul(int a, int b) {
	return (int)((long long) a * b % md);
}

signed main(){

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	vector<vector<array<int, 3>>>dp(n, vector<array<int, 3>>(m + 1));
	//ncc, sum, used endpoints
	dp[1][0][0] = 1; 
	dp[1][0][1] = 2;
	for (int i = 1; i < n; ++i) {
		vector<vector<array<int, 3>>>pd(n, vector<array<int, 3>>(m + 1));
		for (int j = 1; j < n; ++j) {
			for(int k = 0; k <= m; ++k) {
				for(int e = 0; e < 3; ++e){
					int diff = (2 * j - e) * (a[i] - a[i-1]); 
					if(k + diff > m){
						continue; 
					}
					//merge two cc
					if(j > 1) {
						add(pd[j - 1][k + diff][e], mul(j - 1, dp[j][k][e]));
					}
					//create a cc 
					if(j + 1 < n) {
						add(pd[j + 1][k + diff][e], mul(j + 1 - e, dp[j][k][e]));
					}
					//create a cc on the endpoints
					if(j + 1 < n && e < 2){
						add(pd[j + 1][k + diff][e + 1], mul(2 - e, dp[j][k][e]));
					}
					//add to the left or right to an already existing component but not become an endpoint
					add(pd[j][k + diff][e], mul(2 * j - e, dp[j][k][e]));
					//add to the left or right to an already existing component but become an endpoint
					if(e < 2){
						add(pd[j][k + diff][e + 1], mul(2 - e, dp[j][k][e]));
					}
				}
			}
		}
		swap(dp, pd);
	}
	int ans = 0;
	for(int i = 0; i <= m; ++i){
		add(ans, dp[1][i][2]);
	}
	cout << ans << '\n';

}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -