oj.uz

Submission #57150

# Submission time Handle Problem Language Result Execution time Memory
57150 2018-07-14T07:14:36 Z 김세빈(#1653) Skyscraper (JOI16_skyscraper) C++11
0 / 100
 4 ms 832 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

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

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

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:17: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:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", A+i);
   ~~~~~^~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 748 KB Output is correct
2 Incorrect 4 ms 832 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -