oj.uz

Submission #57159

# Submission time Handle Problem Language Result Execution time Memory
57159 2018-07-14T07:30:26 Z 김세빈(#1653) Skyscraper (JOI16_skyscraper) C++11
20 / 100
 2000 ms 93808 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;
const int c = 101010;

int D[2][111][3][220202];
int A[111];
int n, k, ans;

int main()
{
	int i, j, l, x;
	
	scanf("%d%d", &n, &k);
	
	for(i=1;i<=n;i++){
		scanf("%d", A+i);
	}
	
	if(n == 1){
		printf("1\n");
		return 0;
	}
	
	sort(A+1, A+n+1);
	
	for(i=n;i>=1;i--) A[i] -= A[1];
	
	D[0][0][0][0 + c] = 1;
	
	for(i=1;i<n;i++){
		for(j=0;j<=i;j++){
			for(l=-101010;l<=101010;l++){
				// endpoints
				if(j){
					D[i&1][j-1][1][l + A[i] + c] = (D[i&1][j-1][1][l + A[i] + c] + D[~i&1][j][0][l + c] * (ll)2) % mod;
				}
				D[i&1][j][1][l - A[i] + c] = (D[i&1][j][1][l - A[i] + c] + D[~i&1][j][0][l + c] * (ll)2) % mod;
				
				
				if(j){
					D[i&1][j-1][2][l + A[i] + c] = (D[i&1][j-1][2][l + A[i] + c] + D[~i&1][j][1][l + c]) % mod;
					D[i&1][j-1][1][l + 2*A[i] + c] = (D[i&1][j-1][1][l + 2*A[i] + c] + D[~i&1][j][1][l + c]) % mod;
				}
				D[i&1][j][2][l - A[i] + c] = (D[i&1][j][2][l - A[i] + c] + D[~i&1][j][1][l + c]) % mod;
				D[i&1][j][1][l + c] = (D[i&1][j][1][l + c] + D[~i&1][j][1][l + c]) % mod;
				
				
				if(j){
					D[i&1][j-1][2][l + 2*A[i] + c] = (D[i&1][j-1][2][l + 2*A[i] + c] + D[~i&1][j][2][l + c] * (ll)2) % mod;
				}
				D[i&1][j][2][l + c] = (D[i&1][j][2][l + c] + D[~i&1][j][2][l + c] * (ll)2) % mod;
				
				
				for(x=0;x<3;x++){
					// new group
					D[i&1][j+1][x][l - 2*A[i] + c] = (D[i&1][j+1][x][l - 2*A[i] + c] + D[~i&1][j][x][l + c] * (ll)(j + 1)) % mod;
					
					// merge two groups
					if(j > 1){
						D[i&1][j-1][x][l + 2*A[i] + c] = (D[i&1][j-1][x][l + 2*A[i] + c] + D[~i&1][j][x][l + c] * (ll)(j - 1)) % mod;
					}
					
					// group endpoints
					D[i&1][j][x][l + c] = (D[i&1][j][x][l + c] + D[~i&1][j][x][l + c] * (ll)2 * j) % mod;
					
					D[~i&1][j][x][l + c] = 0;
				}
			}
		}
	}
	
	for(l=-101010;l<=101010;l++){
		if(0 <= l + A[n] * 2 && l + A[n] * 2 <= k) ans = (ans + D[~n&1][0][2][l + c]) % mod;
		if(0 <= l + A[n] && l + A[n] <= k) ans = (ans + D[~n&1][0][1][l + c]) % mod;
	}
	
	printf("%d\n", ans);
	
	return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", A+i);
   ~~~~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 35 ms 12260 KB Output is correct
3 Correct 60 ms 17096 KB Output is correct
4 Correct 206 ms 31428 KB Output is correct
5 Correct 350 ms 41632 KB Output is correct
6 Correct 347 ms 41632 KB Output is correct
7 Correct 467 ms 41632 KB Output is correct
8 Correct 333 ms 41632 KB Output is correct
9 Correct 430 ms 41632 KB Output is correct
10 Correct 512 ms 41632 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 785 ms 60420 KB Output is correct
2 Correct 963 ms 70076 KB Output is correct
3 Correct 975 ms 70076 KB Output is correct
4 Correct 1134 ms 70128 KB Output is correct
5 Correct 1411 ms 70128 KB Output is correct
6 Correct 1271 ms 70128 KB Output is correct
7 Correct 1054 ms 70128 KB Output is correct
8 Correct 1115 ms 70128 KB Output is correct
9 Correct 1170 ms 70128 KB Output is correct
10 Correct 1026 ms 70128 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 35 ms 12260 KB Output is correct
3 Correct 60 ms 17096 KB Output is correct
4 Correct 206 ms 31428 KB Output is correct
5 Correct 350 ms 41632 KB Output is correct
6 Correct 347 ms 41632 KB Output is correct
7 Correct 467 ms 41632 KB Output is correct
8 Correct 333 ms 41632 KB Output is correct
9 Correct 430 ms 41632 KB Output is correct
10 Correct 512 ms 41632 KB Output is correct
11 Correct 785 ms 60420 KB Output is correct
12 Correct 963 ms 70076 KB Output is correct
13 Correct 975 ms 70076 KB Output is correct
14 Correct 1134 ms 70128 KB Output is correct
15 Correct 1411 ms 70128 KB Output is correct
16 Correct 1271 ms 70128 KB Output is correct
17 Correct 1054 ms 70128 KB Output is correct
18 Correct 1115 ms 70128 KB Output is correct
19 Correct 1170 ms 70128 KB Output is correct
20 Correct 1026 ms 70128 KB Output is correct
21 Execution timed out 2069 ms 93808 KB Time limit exceeded
22 Halted 0 ms 0 KB -