Submission #585330

#	Time	Username	Problem	Language	Result	Execution time	Memory
585330		Ace	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	154 ms	122784 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e2;
const int L = 1e3;
const ll MOD = 1e9+7;

ll dmod(ll x){
	return x%MOD;
}

int n,l;
int a[N+5];
int memo[N+2][N+2][L+2][3];

int dp(int x, int cc, int sisa, int tepi){
	if(sisa < 0) return 0;
//	printf(">> %d %d %d %d\n", x, cc, sisa, tepi);
	if(x > n){
		if(tepi == 2 && cc == 1) return 1;
		return 0;
	}
	if(tepi == 2 && cc == 1) return 0;
	int &ret = memo[x][cc][sisa][tepi];
	if(ret != -1) return ret;
	ret = 0;
	// nambah cc
	ret = dmod(ret + dmod((ll)(cc+1ll - tepi) * dp(x+1,cc+1,sisa-(2*(cc+1) - tepi)*(a[x+1]-a[x]),tepi)));
	if(tepi < 2) ret = dmod(ret + dmod((ll)(2ll-tepi)*dp(x+1,cc+1,sisa-(2*(cc+1) - tepi - 1)*(a[x+1]-a[x]),tepi+1)));
	// kiri kanan cc
	ret = dmod(ret + dmod((ll)(2ll*cc-tepi) * dp(x+1, cc, sisa-(2*cc - tepi)*(a[x+1]-a[x]),tepi)));
	if(tepi < 2 && cc > 0) ret = dmod(ret + dmod((ll)(2ll-tepi)*dp(x+1,cc,sisa-(2*cc - tepi - 1)*(a[x+1]-a[x]),tepi+1)));
	// join cc
	if(cc >= 2) ret = dmod(ret + dmod((ll)(cc-1ll)*dp(x+1, cc-1, sisa-(2*(cc-1) - tepi)*(a[x+1]-a[x]), tepi)));
//	printf(">> %d %d %d %d = %d\n", x, cc, sisa, tepi, ret);
	return ret;
}

int main(){
	memset(memo,-1,sizeof(memo));
	scanf("%d%d",&n,&l);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	sort(a+1,a+n+1);
	a[n+1] = a[n];
	int ans = dp(1,0,l,0);
	if(n == 1) ans = 1;
	printf("%d\n",ans);
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  scanf("%d%d",&n,&l);
      |  ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   scanf("%d",&a[i]);
      |   ~~~~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80