oj.uz

Submission #51144

# Submission time Handle Problem Language Result Execution time Memory
51144 2018-06-16T23:27:20 Z spencercompton Skyscraper (JOI16_skyscraper) C++17
15 / 100
 920 ms 190448 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[14][101][1<<14];
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++){
		for(int j = 0; j<=l; j++){
			for(int k = 0; k<maxi; k++){
				dp[i][j][k] = -1LL;
			}
		}
	}
	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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 3 ms 712 KB Output is correct
4 Correct 6 ms 5212 KB Output is correct
5 Runtime error 38 ms 24160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 40332 KB Output is correct
2 Correct 164 ms 186768 KB Output is correct
3 Correct 609 ms 186768 KB Output is correct
4 Correct 163 ms 188676 KB Output is correct
5 Correct 139 ms 190448 KB Output is correct
6 Correct 599 ms 190448 KB Output is correct
7 Correct 61 ms 190448 KB Output is correct
8 Correct 463 ms 190448 KB Output is correct
9 Correct 920 ms 190448 KB Output is correct
10 Correct 157 ms 190448 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 600 KB Output is correct
3 Correct 3 ms 712 KB Output is correct
4 Correct 6 ms 5212 KB Output is correct
5 Runtime error 38 ms 24160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -