oj.uz

답안 #57135

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
57135 2018-07-14T06:23:31 Z 김세빈(#1653) Skyscraper (JOI16_skyscraper) C++11
0 / 100
 45 ms 10852 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

ll D[2][111][2][2][10101];
ll A[111];
ll n, k, ans;

int main()
{
	ll i, j, l, x, y;
	
	scanf("%lld%lld", &n, &k);
	
	for(i=1;i<=n;i++){
		scanf("%lld", A+i);
	}
	
	sort(A+1, A+n+1);
	
	for(i=n;i>=1;i--) A[i] -= A[1];
	
	D[0][0][0][0][0 + c] = 1;
	
	for(i=1;i<n;i++){
		for(j=0;j<=i;j++){
			for(l=-3030;l<=3030;l++){
				// endpoints
				if(j){
					D[i&1][j-1][1][0][l + A[i] + c] = (D[i&1][j-1][1][0][l + A[i] + c] + D[~i&1][j][0][0][l + c]) % mod;
					D[i&1][j-1][0][1][l + A[i] + c] = (D[i&1][j-1][0][1][l + A[i] + c] + D[~i&1][j][0][0][l + c]) % mod;
				}
				D[i&1][j][1][0][l - A[i] + c] = (D[i&1][j][1][0][l - A[i] + c] + D[~i&1][j][0][0][l + c]) % mod;
				D[i&1][j][0][1][l - A[i] + c] = (D[i&1][j][0][1][l - A[i] + c] + D[~i&1][j][0][0][l + c]) % mod;
				
				
				if(j){
					D[i&1][j-1][1][1][l + A[i] + c] = (D[i&1][j-1][1][1][l + A[i] + c] + D[~i&1][j][0][1][l + c]) % mod;
					D[i&1][j-1][0][1][l + 2*A[i] + c] = (D[i&1][j-1][0][1][l + 2*A[i] + c] + D[~i&1][j][0][1][l + c]) % mod;
				}
				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][1][l + c]) % mod;
				D[i&1][j][0][1][l + c] = (D[i&1][j][0][1][l + c] + D[~i&1][j][0][1][l + c]) % mod;
				
				
				if(j){
					D[i&1][j-1][1][0][l + 2*A[i] + c] = (D[i&1][j-1][1][0][l + 2*A[i] + c] + D[~i&1][j][1][0][l + c]) % mod;
					D[i&1][j-1][1][1][l + A[i] + c] = (D[i&1][j-1][1][1][l + A[i] + c] + D[~i&1][j][1][0][l + c]) % mod;
				}
				D[i&1][j][1][0][l + c] = (D[i&1][j][1][0][l + c] + D[~i&1][j][1][0][l + c]) % mod;
				D[i&1][j][1][1][l - A[i] + c] = (D[i&1][j][1][1][l - A[i] + c] + D[~i&1][j][1][0][l + c]) % mod;
				
				
				if(j){
					D[i&1][j-1][1][1][l + 2*A[i] + c] = (D[i&1][j-1][1][1][l + 2*A[i] + c] + D[~i&1][j][1][1][l + c] * 2) % mod;
				}
				D[i&1][j][1][1][l + c] = (D[i&1][j][1][1][l + c] + D[~i&1][j][1][1][l + c] * 2) % mod;
				
				
				for(x=0;x<2;x++) for(y=0;y<2;y++){
					// new group
					D[i&1][j+1][x][y][l - 2*A[i] + c] = (D[i&1][j+1][x][y][l - 2*A[i] + c] + D[~i&1][j][x][y][l + c] * (j + 1)) % mod;
					
					// merge two groups
					if(j > 1){
						D[i&1][j-1][x][y][l + 2*A[i] + c] = (D[i&1][j-1][x][y][l + 2*A[i] + c] + D[~i&1][j][x][y][l + c] * (j - 1)) % mod;
					}
					
					// group endpoints
					D[i&1][j][x][y][l + c] = (D[i&1][j][x][y][l + c] + D[~i&1][j][x][y][l + c] * 2 * j) % mod;
					
					D[~i&1][j][x][y][l + c] = 0;
				}
			}
		}
	}
	
	for(l=-3030;l<=3030;l++){
		if(0 <= l + A[n] * 2 && l + A[n] * 2 <= k) ans = (ans + D[~n&1][0][1][1][l + c]) % mod;
		if(0 <= l + A[n] && l + A[n] <= k) ans = (ans + D[~n&1][0][1][0][l + c]) % mod;
		if(0 <= l + A[n] && l + A[n] <= k) ans = (ans + D[~n&1][0][0][1][l + c]) % mod;
	}
	
	printf("%lld\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("%lld%lld", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", A+i);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 45 ms 10852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -