Submission #545686

#	Time	Username	Problem	Language	Result	Execution time	Memory
545686		MilosMilutinovic	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	306 ms	2768 KiB

skyscraper

#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<typename T> bool chkmax(T&x,T y){return x<y?x=y,1:0;}
template<typename T> bool chkmin(T&x,T y){return x>y?x=y,1:0;}

const int md=1e9+7;
int n,l,a[105],dp[105][1005][3],tmp[105][1005][3];

void chkadd(int&x,int y){x+=y; if(x>=md) x-=md;}
int mul(int x,int y){return (ll)x*y%md;}

int main(){
	scanf("%d%d",&n,&l);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	if(n==1){printf("1"); return 0;}
	sort(a+1,a+n+1);
	if((a[2]-a[1])*2<=l) dp[1][(a[2]-a[1])*2][0]=1;
	if(a[2]-a[1]<=l) dp[1][a[2]-a[1]][1]=2;
	for(int i=2;i<=n;i++){
		int d=a[i+1]-a[i];
		for(int j=1;j<=n;j++)
			for(int s=0;s<=l;s++)
				for(int k=0;k<=2;k++)
					tmp[j][s][k]=dp[j][s][k],dp[j][s][k]=0;
		for(int j=1;j<=n;j++){
			for(int s=0;s<=l;s++){
				for(int k=0;k<=2;k++){
					int v=tmp[j][s][k];
					//dodajem bez spajanja, nema novih krajeva
					int ns=s+d*(2*j-k);
					if(ns>=0&&ns<=l) chkadd(dp[j][ns][k],mul(v,2*j-k));
					//spajam, nema novih krajeva
					ns=s+d*(2*j-k-2);
					if(ns>=0&&j>1&&ns<=l) chkadd(dp[j-1][ns][k],mul(v,j-1));
					//pravim novu komponentu, nema novih krajeva
					ns=s+d*(2*j-k+2);
					if(ns>=0&&j<n&&ns<=l) chkadd(dp[j+1][ns][k],mul(v,j+1-k));
					//dodajem bez spajanja, ima novi kraj
					ns=s+d*(2*j-k-1);
					if(ns>=0&&k<2&&ns<=l) chkadd(dp[j][ns][k+1],mul(v,2-k));
					//pravim novu komponentu, ima novi kraj
					ns=s+d*(2*j-k+1);
					if(ns>=0&&k<2&&ns<=l) chkadd(dp[j+1][ns][k+1],mul(v,2-k));
				}
			}
		}
	}
	int ans=0;
	for(int i=0;i<=l;i++) chkadd(ans,dp[1][i][2]);
	printf("%d",ans);
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  scanf("%d%d",&n,&l);
      |  ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:26:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
      |                        ~~~~~^~~~~~~~~~~~

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