oj.uz

Submission #99232

# Submission time Handle Problem Language Result Execution time Memory
99232 2019-03-01T19:49:32 Z TadijaSebez Skyscraper (JOI16_skyscraper) C++11
15 / 100
 7 ms 2816 KB 
#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;
	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) continue;
						//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

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 7 ms 2688 KB Output is correct
3 Correct 6 ms 2560 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 5 ms 2688 KB Output is correct
6 Correct 7 ms 2816 KB Output is correct
7 Correct 4 ms 2432 KB Output is correct
8 Correct 5 ms 2684 KB Output is correct
9 Correct 7 ms 2816 KB Output is correct
10 Correct 6 ms 2688 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2432 KB Output isn't correct
2 Halted 0 ms 0 KB -