oj.uz

Submission #401002

# Submission time Handle Problem Language Result Execution time Memory
401002 2021-05-09T05:49:34 Z gaurav172 Skyscraper (JOI16_skyscraper) C++14
100 / 100
 371 ms 160268 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;   
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) (ll)(a.size())
const int M = 101;
const int mod = 1e9+7;
int a[M],n,L;
int dp[101][1001][2][101][2];

int solve(int id, int l, int kl, int k, int kr)
{
	int nl = l;
	if(id > 1)
	{
		nl += (kl + kr + 2*k)*(a[id] - a[id-1]);
	}
	if(nl > L)
		return 0;

	if(id == n)
	{
		if(k)
			return 0;
		else
			return 1;
	}

	if(dp[id][l][kl][k][kr] != -1)
		return dp[id][l][kl][k][kr];
	
	int res = 0;

	// add to the left segment
	res = (res + solve(id + 1, nl, 1, k, kr))%mod;
	// add to left and merge with middle
	if(k)
		res = (res + (k*1LL*solve(id + 1, nl, 1, k - 1, kr))%mod)%mod;

	// add to the right segment
	res = (res + solve(id + 1, nl, kl, k, 1))%mod;
	// add to right and merge with middle
	if(k)
		res = (res + (k*1LL*solve(id + 1, nl, kl, k - 1, 1))%mod)%mod;

	// create new in the middle
	res = (res + solve(id + 1, nl, kl , k + 1, kr))%mod;

	// add to some segment in the middle
	if(k)
		res = (res + (k*2LL*solve(id + 1, nl, kl, k, kr))%mod)%mod;

	// merge two middle segments
	if(k >= 2)
		res = (res + (k*(k-1)*1LL*solve(id + 1, nl, kl, k-1, kr))%mod)%mod;

	return dp[id][l][kl][k][kr] = res;
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>L;

	for(int i=1;i<=n;i++)
		cin>>a[i];

	sort(a+1, a+n+1);
	memset(dp, -1, sizeof(dp));
	cout<<solve(1, 0, 0, 0, 0)<<"\n";
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 160068 KB Output is correct
2 Correct 72 ms 160044 KB Output is correct
3 Correct 74 ms 160092 KB Output is correct
4 Correct 74 ms 160104 KB Output is correct
5 Correct 81 ms 160092 KB Output is correct
6 Correct 74 ms 160160 KB Output is correct
7 Correct 73 ms 160068 KB Output is correct
8 Correct 73 ms 160048 KB Output is correct
9 Correct 73 ms 160048 KB Output is correct
10 Correct 92 ms 160116 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 160096 KB Output is correct
2 Correct 76 ms 160048 KB Output is correct
3 Correct 74 ms 160148 KB Output is correct
4 Correct 74 ms 160116 KB Output is correct
5 Correct 73 ms 160156 KB Output is correct
6 Correct 74 ms 160060 KB Output is correct
7 Correct 86 ms 160072 KB Output is correct
8 Correct 75 ms 160148 KB Output is correct
9 Correct 77 ms 160100 KB Output is correct
10 Correct 75 ms 160060 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 160068 KB Output is correct
2 Correct 72 ms 160044 KB Output is correct
3 Correct 74 ms 160092 KB Output is correct
4 Correct 74 ms 160104 KB Output is correct
5 Correct 81 ms 160092 KB Output is correct
6 Correct 74 ms 160160 KB Output is correct
7 Correct 73 ms 160068 KB Output is correct
8 Correct 73 ms 160048 KB Output is correct
9 Correct 73 ms 160048 KB Output is correct
10 Correct 92 ms 160116 KB Output is correct
11 Correct 76 ms 160096 KB Output is correct
12 Correct 76 ms 160048 KB Output is correct
13 Correct 74 ms 160148 KB Output is correct
14 Correct 74 ms 160116 KB Output is correct
15 Correct 73 ms 160156 KB Output is correct
16 Correct 74 ms 160060 KB Output is correct
17 Correct 86 ms 160072 KB Output is correct
18 Correct 75 ms 160148 KB Output is correct
19 Correct 77 ms 160100 KB Output is correct
20 Correct 75 ms 160060 KB Output is correct
21 Correct 73 ms 160060 KB Output is correct
22 Correct 371 ms 160168 KB Output is correct
23 Correct 135 ms 160256 KB Output is correct
24 Correct 172 ms 160068 KB Output is correct
25 Correct 146 ms 160156 KB Output is correct
26 Correct 135 ms 160172 KB Output is correct
27 Correct 133 ms 160268 KB Output is correct
28 Correct 146 ms 160068 KB Output is correct
29 Correct 217 ms 160168 KB Output is correct
30 Correct 143 ms 160164 KB Output is correct