oj.uz

Submission #57206

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

using namespace std;

typedef long long ll;

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

int D[2][111][3][110101];
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=-c;l<=c;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=-c;l<=c;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 3 ms 376 KB Output is correct
2 Correct 16 ms 6356 KB Output is correct
3 Correct 43 ms 8860 KB Output is correct
4 Correct 139 ms 15984 KB Output is correct
5 Correct 226 ms 21308 KB Output is correct
6 Correct 218 ms 21388 KB Output is correct
7 Correct 219 ms 21388 KB Output is correct
8 Correct 264 ms 21388 KB Output is correct
9 Correct 179 ms 21388 KB Output is correct
10 Correct 188 ms 21388 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 30560 KB Output is correct
2 Correct 480 ms 35396 KB Output is correct
3 Correct 572 ms 35396 KB Output is correct
4 Correct 452 ms 35440 KB Output is correct
5 Correct 625 ms 35440 KB Output is correct
6 Correct 664 ms 35440 KB Output is correct
7 Correct 518 ms 35440 KB Output is correct
8 Correct 480 ms 35440 KB Output is correct
9 Correct 473 ms 35440 KB Output is correct
10 Correct 493 ms 35484 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 16 ms 6356 KB Output is correct
3 Correct 43 ms 8860 KB Output is correct
4 Correct 139 ms 15984 KB Output is correct
5 Correct 226 ms 21308 KB Output is correct
6 Correct 218 ms 21388 KB Output is correct
7 Correct 219 ms 21388 KB Output is correct
8 Correct 264 ms 21388 KB Output is correct
9 Correct 179 ms 21388 KB Output is correct
10 Correct 188 ms 21388 KB Output is correct
11 Correct 488 ms 30560 KB Output is correct
12 Correct 480 ms 35396 KB Output is correct
13 Correct 572 ms 35396 KB Output is correct
14 Correct 452 ms 35440 KB Output is correct
15 Correct 625 ms 35440 KB Output is correct
16 Correct 664 ms 35440 KB Output is correct
17 Correct 518 ms 35440 KB Output is correct
18 Correct 480 ms 35440 KB Output is correct
19 Correct 473 ms 35440 KB Output is correct
20 Correct 493 ms 35484 KB Output is correct
21 Execution timed out 2082 ms 61884 KB Time limit exceeded
22 Halted 0 ms 0 KB -