oj.uz

Submission #598130

# Submission time Handle Problem Language Result Execution time Memory
598130 2022-07-17T16:51:15 Z CSQ31 Skyscraper (JOI16_skyscraper) C++17
100 / 100
 242 ms 320108 KB 
#include <bits/stdc++.h>
using namespace std;
int a[101];
typedef long long int ll;
const int MOD = 1e9+7;
ll dp[2][2][101][101][1001],n,L;
//left border chosen?
//right border chosen?
//we are currently deciding where is i
//there are cnt comps
//total cost right now is cost
ll solve(int lf,int rg,int i,int cnt,int cost){
	 //#total if we start from this state
	if(cnt<0)return 0;
	if(dp[lf][rg][i][cnt][cost] != -1)return dp[lf][rg][i][cnt][cost];
	//replace everyt "?" with a[i]
	int ocost = cost;
	if(i)cost+=(2*cnt + lf + rg) * (a[i]-a[i-1]);
	if(cost > L )return 0;
	if(i==n-1)return cnt == 0;	
	ll res = 0;
	res += solve(lf,rg,i+1,cnt+1,cost); //single comp  b i b 
    res += solve(lf,rg,i+1,cnt,cost) * (cnt+lf); //attach to right side of smtg s i b
    res += solve(lf,rg,i+1,cnt,cost) * (cnt+rg); //attach to left side of smtg b i s
    if(!lf){
		res += solve(1,rg,i+1,cnt,cost); //make you left border
		res += solve(1,rg,i+1,cnt-1,cost)*cnt; //and also merge with smtg
	}
    if(!rg){
		res += solve(lf,1,i+1,cnt,cost); //make you right border 
		res += solve(lf,1,i+1,cnt-1,cost) * cnt; //and also merge with smtg
	}
    
    if(lf && cnt)res += solve(lf,rg,i+1,cnt-1,cost) * cnt;  //merge smtg with left border
    if(rg && cnt)res += solve(lf,rg,i+1,cnt-1,cost) * cnt;  //merge smtg with right border
    if(cnt>1) res += solve(lf,rg,i+1,cnt-1,cost) * cnt*(cnt-1); //s i s //merge two non border guys
    res%=MOD;
    return dp[lf][rg][i][cnt][ocost] = res%MOD;
    
}
int main()
{
	cin>>n>>L;
	for(int i=0;i<n;i++)cin>>a[i];
	sort(a,a+n);
	memset(dp,-1,sizeof(dp));
	cout<<solve(0,0,0,0,0);
	
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 319912 KB Output is correct
2 Correct 119 ms 319972 KB Output is correct
3 Correct 125 ms 319904 KB Output is correct
4 Correct 118 ms 319948 KB Output is correct
5 Correct 114 ms 320092 KB Output is correct
6 Correct 114 ms 319992 KB Output is correct
7 Correct 117 ms 319996 KB Output is correct
8 Correct 119 ms 319948 KB Output is correct
9 Correct 116 ms 319944 KB Output is correct
10 Correct 116 ms 319980 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 320068 KB Output is correct
2 Correct 116 ms 319956 KB Output is correct
3 Correct 111 ms 319956 KB Output is correct
4 Correct 113 ms 319964 KB Output is correct
5 Correct 127 ms 319988 KB Output is correct
6 Correct 117 ms 319948 KB Output is correct
7 Correct 114 ms 319900 KB Output is correct
8 Correct 113 ms 319896 KB Output is correct
9 Correct 119 ms 319908 KB Output is correct
10 Correct 118 ms 319984 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 319912 KB Output is correct
2 Correct 119 ms 319972 KB Output is correct
3 Correct 125 ms 319904 KB Output is correct
4 Correct 118 ms 319948 KB Output is correct
5 Correct 114 ms 320092 KB Output is correct
6 Correct 114 ms 319992 KB Output is correct
7 Correct 117 ms 319996 KB Output is correct
8 Correct 119 ms 319948 KB Output is correct
9 Correct 116 ms 319944 KB Output is correct
10 Correct 116 ms 319980 KB Output is correct
11 Correct 121 ms 320068 KB Output is correct
12 Correct 116 ms 319956 KB Output is correct
13 Correct 111 ms 319956 KB Output is correct
14 Correct 113 ms 319964 KB Output is correct
15 Correct 127 ms 319988 KB Output is correct
16 Correct 117 ms 319948 KB Output is correct
17 Correct 114 ms 319900 KB Output is correct
18 Correct 113 ms 319896 KB Output is correct
19 Correct 119 ms 319908 KB Output is correct
20 Correct 118 ms 319984 KB Output is correct
21 Correct 116 ms 319940 KB Output is correct
22 Correct 242 ms 320008 KB Output is correct
23 Correct 191 ms 319992 KB Output is correct
24 Correct 202 ms 320012 KB Output is correct
25 Correct 207 ms 320108 KB Output is correct
26 Correct 178 ms 320012 KB Output is correct
27 Correct 152 ms 320064 KB Output is correct
28 Correct 174 ms 320084 KB Output is correct
29 Correct 201 ms 320068 KB Output is correct
30 Correct 192 ms 320020 KB Output is correct