Submission #51147

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
51147	2018-06-16T23:30:58 Z	spencercompton	Skyscraper (JOI16_skyscraper)	C++17	20 / 100	1297 ms	191544 KB

skyscraper

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// ll dp[14][1001][1<<14];
vector<vector<vector<ll> > > dp;
int n, l;
int ar[100];
ll mod = 1000000007LL;
ll go(int mask, int rem, int last){
	if(rem<0){
		return 0LL;
	}
	if(mask==0){
		return 1LL;
	}
	if(dp[last][rem][mask]!=-1LL){
		return dp[last][rem][mask];
	}
	ll ret = 0LL;
	for(int i = 0; i<n; i++){
		if((mask&(1<<i))!=0){
			ret += go(mask-(1<<i), rem-abs(ar[i]-ar[last]),i);
		}
	}
	ret %= mod;
	dp[last][rem][mask] = ret;
	return ret;
}
int main(){
	cin >> n >> l;
	for(int i = 0; i<n; i++){
		cin >> ar[i];
	}
	int maxi = (1<<n);
	for(int i = 0; i<n; i++){
		vector<vector<ll> > a;
		for(int j = 0; j<=l; j++){
			vector<ll> b;
			for(int k = 0; k<maxi; k++){
				b.push_back(-1LL);
			}
			a.push_back(b);
		}
		dp.push_back(a);
	}
	ll ret = 0;
	for(int i = 0; i<n; i++){
		ret += go(maxi-1-(1<<i), l, i);
	}
	ret %= mod;
	cout << ret << endl;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	476 KB	Output is correct
3	Correct	2 ms	476 KB	Output is correct
4	Correct	3 ms	672 KB	Output is correct
5	Correct	28 ms	17736 KB	Output is correct
6	Correct	25 ms	17736 KB	Output is correct
7	Correct	8 ms	17736 KB	Output is correct
8	Correct	5 ms	17736 KB	Output is correct
9	Correct	28 ms	17736 KB	Output is correct
10	Correct	6 ms	17736 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	109 ms	27360 KB	Output is correct
2	Correct	309 ms	187704 KB	Output is correct
3	Correct	695 ms	187704 KB	Output is correct
4	Correct	304 ms	189536 KB	Output is correct
5	Correct	280 ms	191544 KB	Output is correct
6	Correct	854 ms	191544 KB	Output is correct
7	Correct	103 ms	191544 KB	Output is correct
8	Correct	628 ms	191544 KB	Output is correct
9	Correct	1297 ms	191544 KB	Output is correct
10	Correct	304 ms	191544 KB	Output is correct

Subtask #3

0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	476 KB	Output is correct
3	Correct	2 ms	476 KB	Output is correct
4	Correct	3 ms	672 KB	Output is correct
5	Correct	28 ms	17736 KB	Output is correct
6	Correct	25 ms	17736 KB	Output is correct
7	Correct	8 ms	17736 KB	Output is correct
8	Correct	5 ms	17736 KB	Output is correct
9	Correct	28 ms	17736 KB	Output is correct
10	Correct	6 ms	17736 KB	Output is correct
11	Correct	109 ms	27360 KB	Output is correct
12	Correct	309 ms	187704 KB	Output is correct
13	Correct	695 ms	187704 KB	Output is correct
14	Correct	304 ms	189536 KB	Output is correct
15	Correct	280 ms	191544 KB	Output is correct
16	Correct	854 ms	191544 KB	Output is correct
17	Correct	103 ms	191544 KB	Output is correct
18	Correct	628 ms	191544 KB	Output is correct
19	Correct	1297 ms	191544 KB	Output is correct
20	Correct	304 ms	191544 KB	Output is correct
21	Runtime error	14 ms	191544 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Halted	0 ms	0 KB	-