oj.uz

Submission #99236

# Submission time Handle Problem Language Result Execution time Memory
99236 2019-03-01T19:54:41 Z TadijaSebez Skyscraper (JOI16_skyscraper) C++11
100 / 100
 1607 ms 126824 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 3 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 2432 KB Output is correct
6 Correct 4 ms 2560 KB Output is correct
7 Correct 4 ms 2432 KB Output is correct
8 Correct 5 ms 2560 KB Output is correct
9 Correct 4 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 5 ms 2688 KB Output is correct
2 Correct 7 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 5 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 7 ms 2816 KB Output is correct
7 Correct 5 ms 2432 KB Output is correct
8 Correct 6 ms 2688 KB Output is correct
9 Correct 9 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 3 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 2432 KB Output is correct
6 Correct 4 ms 2560 KB Output is correct
7 Correct 4 ms 2432 KB Output is correct
8 Correct 5 ms 2560 KB Output is correct
9 Correct 4 ms 2560 KB Output is correct
10 Correct 5 ms 2560 KB Output is correct
11 Correct 5 ms 2688 KB Output is correct
12 Correct 7 ms 2688 KB Output is correct
13 Correct 6 ms 2688 KB Output is correct
14 Correct 5 ms 2688 KB Output is correct
15 Correct 6 ms 2688 KB Output is correct
16 Correct 7 ms 2816 KB Output is correct
17 Correct 5 ms 2432 KB Output is correct
18 Correct 6 ms 2688 KB Output is correct
19 Correct 9 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 1607 ms 126824 KB Output is correct
23 Correct 587 ms 57116 KB Output is correct
24 Correct 691 ms 67448 KB Output is correct
25 Correct 691 ms 62688 KB Output is correct
26 Correct 535 ms 54504 KB Output is correct
27 Correct 324 ms 32220 KB Output is correct
28 Correct 487 ms 44176 KB Output is correct
29 Correct 934 ms 80380 KB Output is correct
30 Correct 602 ms 62648 KB Output is correct