Submission #99236

#	Time	Username	Problem	Language	Result	Execution time	Memory
99236		TadijaSebez	Skyscraper (JOI16_skyscraper)	C++11	100 / 100	1607 ms	126824 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
int add(int x, int y){ x+=y;return x>=mod?x-mod:x;}
int sub(int x, int y){ x-=y;return x<0?x+mod:x;}
int mul(int x, int y){ return (ll)x*y%mod;}
const int N=105;
map<int,int> dp[N][N][2][2];
int a[N];
int main()
{
	int n,i,L;
	scanf("%i %i",&n,&L);
	for(i=1;i<=n;i++) scanf("%i",&a[i]);
	sort(a+1,a+1+n);
	dp[1][1][0][0][-2*a[1]]=1;
	dp[1][1][1][0][-a[1]]=1;
	dp[1][1][0][1][-a[1]]=1;
	dp[1][1][1][1][0]=1;
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int l=0;l<2;l++)
			{
				for(int r=0;r<2;r++)
				{
					for(auto d:dp[i-1][j][l][r])
					{
						int k=d.first;
						int val=d.second;
						if(k>L || k+(j*2-l-r)*a[i]>L) break;
						//printf("i:%i j:%i l:%i r:%i k:%i val:%i\n",i-1,j,l,r,k,val);
						//Extend
						dp[i][j][l][r][k]=add(dp[i][j][l][r][k],mul(val,j*2-l-r));
						//Left End
						if(!l) dp[i][j][1][r][k+a[i]]=add(dp[i][j][1][r][k+a[i]],val);
						//Right End
						if(!r) dp[i][j][l][1][k+a[i]]=add(dp[i][j][l][1][k+a[i]],val);
						//New Chain
						dp[i][j+1][l][r][k-2*a[i]]=add(dp[i][j+1][l][r][k-2*a[i]],mul(j+1-l-r,val));
						if(!l) dp[i][j+1][1][r][k-a[i]]=add(dp[i][j+1][1][r][k-a[i]],val);
						if(!r) dp[i][j+1][l][1][k-a[i]]=add(dp[i][j+1][l][1][k-a[i]],val);
						//Connect
						if(j>1) dp[i][j-1][l][r][k+2*a[i]]=add(dp[i][j-1][l][r][k+2*a[i]],mul(j-1,val));
					}
				}
			}
		}
	}
	int ans=0;
	for(auto d:dp[n][1][1][1])
	{
		int k=d.first;
		int val=d.second;
		if(k<=L) ans=add(ans,val);
		//printf("(%i %i)\n",k,val);
	}
	printf("%i\n",ans);
	return 0;
}

Compilation message (stderr)

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

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