oj.uz

Submission #99234

# Submission time Handle Problem Language Result Execution time Memory
99234 2019-03-01T19:53:31 Z TadijaSebez Skyscraper (JOI16_skyscraper) C++11
100 / 100
 1602 ms 126944 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 || 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 4 ms 2432 KB Output is correct
5 Correct 4 ms 2560 KB Output is correct
6 Correct 5 ms 2560 KB Output is correct
7 Correct 4 ms 2432 KB Output is correct
8 Correct 5 ms 2432 KB Output is correct
9 Correct 5 ms 2560 KB Output is correct
10 Correct 5 ms 2560 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
80.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 4 ms 2432 KB Output is correct
5 Correct 4 ms 2560 KB Output is correct
6 Correct 5 ms 2560 KB Output is correct
7 Correct 4 ms 2432 KB Output is correct
8 Correct 5 ms 2432 KB Output is correct
9 Correct 5 ms 2560 KB Output is correct
10 Correct 5 ms 2560 KB Output is correct
11 Correct 8 ms 2688 KB Output is correct
12 Correct 6 ms 2688 KB Output is correct
13 Correct 6 ms 2688 KB Output is correct
14 Correct 6 ms 2688 KB Output is correct
15 Correct 6 ms 2688 KB Output is correct
16 Correct 9 ms 2816 KB Output is correct
17 Correct 4 ms 2432 KB Output is correct
18 Correct 5 ms 2660 KB Output is correct
19 Correct 8 ms 2816 KB Output is correct
20 Correct 5 ms 2688 KB Output is correct
21 Correct 7 ms 3072 KB Output is correct
22 Correct 1602 ms 126944 KB Output is correct
23 Correct 587 ms 57108 KB Output is correct
24 Correct 723 ms 67448 KB Output is correct
25 Correct 615 ms 62740 KB Output is correct
26 Correct 547 ms 54604 KB Output is correct
27 Correct 314 ms 32248 KB Output is correct
28 Correct 501 ms 44256 KB Output is correct
29 Correct 959 ms 80448 KB Output is correct
30 Correct 628 ms 62604 KB Output is correct