oj.uz

Submission #559528

# Submission time Handle Problem Language Result Execution time Memory
559528 2022-05-10T06:04:59 Z Pherokung Skyscraper (JOI16_skyscraper) C++14
20 / 100
 128 ms 37560 KB 
#include<bits/stdc++.h>
using namespace std;
#define N 105
#define L 1005
const int mod = 1e9+7;
int n,l,a[N],dp[N][N][L][3],ans=0;
int add(int a,int b){
	return ((a % mod)+(b % mod)) % mod;
}
int mul(int a,int b){
	return ((long long)(a * b)) % mod;
}
int main(){
	scanf("%d%d",&n,&l);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	
	if(n == 1){ // special case
		printf("1");
		return 0;
	}
	
	dp[1][1][0][0] = 1;
	dp[1][1][0][1] = 2;
	for(int idx=1;idx<n;idx++){
		for(int comp=1;comp<=idx;comp++){ 
			for(int sum=0;sum<=l;sum++){ 
				for(int ex=0;ex<=2;ex++){ // ex is number of endpoint(begin/end) which was filled
					int n_sum = sum + (2 * comp - ex) * (a[idx+1] - a[idx]); // add a[idx+1] to every available spaces
					int val = dp[idx][comp][sum][ex];
					if(n_sum > l) continue;
					
					if(ex < 2){
						// add idx+1 to endpoint and merge to some components
						dp[idx+1][comp][n_sum][ex+1] = add(dp[idx+1][comp][n_sum][ex+1], mul((2 - ex), val));
						// add idx+1 to endpoint and create new component
						dp[idx+1][comp+1][n_sum][ex+1] = add(dp[idx+1][comp+1][n_sum][ex+1], mul((2 - ex), val));
					}
					
					// create new component
					dp[idx+1][comp+1][n_sum][ex] = add(dp[idx+1][comp+1][n_sum][ex], mul((comp + 1 - ex), val));
					
					// add to begin or end of component
					dp[idx+1][comp][n_sum][ex] = add(dp[idx+1][comp][n_sum][ex], mul((2 * comp - ex), val));
					
					// add and merge between two components
					dp[idx+1][comp-1][n_sum][ex] = add(dp[idx+1][comp-1][n_sum][ex], mul((comp - 1), val));
				}
			}
		}
	}
	
	for(int i=0;i<=l;i++) ans = add(ans, dp[n][1][i][2]);
	printf("%d",ans);
}

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]
   14 |  scanf("%d%d",&n,&l);
      |  ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:15:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
      |                        ~~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 1 ms 468 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 724 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Correct 1 ms 852 KB Output is correct
17 Correct 1 ms 724 KB Output is correct
18 Correct 1 ms 852 KB Output is correct
19 Correct 1 ms 852 KB Output is correct
20 Correct 1 ms 724 KB Output is correct
21 Correct 2 ms 3156 KB Output is correct
22 Incorrect 128 ms 37560 KB Output isn't correct
23 Halted 0 ms 0 KB -