oj.uz

Submission #99235

# Submission time Handle Problem Language Result Execution time Memory
99235 2019-03-01T19:54:07 Z TadijaSebez Skyscraper (JOI16_skyscraper) C++11
20 / 100
 2000 ms 171648 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;
	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) break;// || 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

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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2432 KB Output is correct
2 Correct 4 ms 2432 KB Output is correct
3 Correct 4 ms 2432 KB Output is correct
4 Correct 5 ms 2560 KB Output is correct
5 Correct 16 ms 3712 KB Output is correct
6 Correct 12 ms 3840 KB Output is correct
7 Correct 9 ms 3200 KB Output is correct
8 Correct 6 ms 2560 KB Output is correct
9 Correct 12 ms 3712 KB Output is correct
10 Correct 6 ms 2688 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2944 KB Output is correct
2 Correct 50 ms 7288 KB Output is correct
3 Correct 12 ms 3456 KB Output is correct
4 Correct 57 ms 7132 KB Output is correct
5 Correct 62 ms 8056 KB Output is correct
6 Correct 32 ms 5368 KB Output is correct
7 Correct 17 ms 4096 KB Output is correct
8 Correct 11 ms 3456 KB Output is correct
9 Correct 14 ms 3584 KB Output is correct
10 Correct 39 ms 6364 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2432 KB Output is correct
2 Correct 4 ms 2432 KB Output is correct
3 Correct 4 ms 2432 KB Output is correct
4 Correct 5 ms 2560 KB Output is correct
5 Correct 16 ms 3712 KB Output is correct
6 Correct 12 ms 3840 KB Output is correct
7 Correct 9 ms 3200 KB Output is correct
8 Correct 6 ms 2560 KB Output is correct
9 Correct 12 ms 3712 KB Output is correct
10 Correct 6 ms 2688 KB Output is correct
11 Correct 9 ms 2944 KB Output is correct
12 Correct 50 ms 7288 KB Output is correct
13 Correct 12 ms 3456 KB Output is correct
14 Correct 57 ms 7132 KB Output is correct
15 Correct 62 ms 8056 KB Output is correct
16 Correct 32 ms 5368 KB Output is correct
17 Correct 17 ms 4096 KB Output is correct
18 Correct 11 ms 3456 KB Output is correct
19 Correct 14 ms 3584 KB Output is correct
20 Correct 39 ms 6364 KB Output is correct
21 Correct 563 ms 48892 KB Output is correct
22 Execution timed out 2061 ms 171648 KB Time limit exceeded
23 Halted 0 ms 0 KB -