oj.uz

Submission #287898

# Submission time Handle Problem Language Result Execution time Memory
287898 2020-09-01T06:11:13 Z 임성재(#5782) Skyscraper (JOI16_skyscraper) C++17
20 / 100
 901 ms 499704 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;
const ll Mod = 1e9 + 7;

int n, l;
int a[1010];
int dp[17000][14][1111];

int main() {
	fast;

	cin >> n >> l;

	for(int i=0; i<n; i++) {
		cin >> a[i];
	}

	for(int i=1; i<(1<<n); i++) {
		if(__builtin_popcount(i) == 1) {
			for(int j=0; j<n; j++) {
				if(i == (1<<j)) {
					dp[i][j][0] = 1;
				}
			}
			continue;
		}

		for(int j=0; j<n; j++) {
			if(~i & (1<<j)) continue;

			for(int k=0; k<=l; k++) {
				for(int m=0; m<n; m++) {
					if(m == j) continue;
					if(~i & (1<<m)) continue;
					if(abs(a[m] - a[j]) > k) continue;
					
					dp[i][j][k] += dp[i ^ (1<<j)][m][k - abs(a[m] - a[j])];
					dp[i][j][k] %= Mod;
				}
			}
		}
	}

	ll ans = 0;
	for(int i=0; i<n; i++) {
		for(int j=0; j<=l; j++) {
			ans += dp[(1<<n)-1][i][j];
			ans %= Mod;
		}
	}

	cout << ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 1152 KB Output is correct
5 Correct 26 ms 6264 KB Output is correct
6 Correct 23 ms 6136 KB Output is correct
7 Correct 8 ms 4864 KB Output is correct
8 Correct 6 ms 4736 KB Output is correct
9 Correct 25 ms 6264 KB Output is correct
10 Correct 7 ms 4864 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 105084 KB Output is correct
2 Correct 898 ms 498948 KB Output is correct
3 Correct 647 ms 479856 KB Output is correct
4 Correct 901 ms 499076 KB Output is correct
5 Correct 884 ms 499704 KB Output is correct
6 Correct 899 ms 498936 KB Output is correct
7 Correct 553 ms 471672 KB Output is correct
8 Correct 633 ms 478456 KB Output is correct
9 Correct 793 ms 492024 KB Output is correct
10 Correct 823 ms 495040 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 1152 KB Output is correct
5 Correct 26 ms 6264 KB Output is correct
6 Correct 23 ms 6136 KB Output is correct
7 Correct 8 ms 4864 KB Output is correct
8 Correct 6 ms 4736 KB Output is correct
9 Correct 25 ms 6264 KB Output is correct
10 Correct 7 ms 4864 KB Output is correct
11 Correct 149 ms 105084 KB Output is correct
12 Correct 898 ms 498948 KB Output is correct
13 Correct 647 ms 479856 KB Output is correct
14 Correct 901 ms 499076 KB Output is correct
15 Correct 884 ms 499704 KB Output is correct
16 Correct 899 ms 498936 KB Output is correct
17 Correct 553 ms 471672 KB Output is correct
18 Correct 633 ms 478456 KB Output is correct
19 Correct 793 ms 492024 KB Output is correct
20 Correct 823 ms 495040 KB Output is correct
21 Incorrect 20 ms 7808 KB Output isn't correct
22 Halted 0 ms 0 KB -