제출 #1204538

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1204538		_rain_	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	124 ms	125376 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=(int)101;
const int L=(int)1001;
const int MOD=(int)1e9+7;
	int add(int a,int b){
		return a+b>=MOD?a+b-MOD:a+b;
	}
	int mul(int a,int b){
		return (LL)a*b%MOD;
	}

	int dp[N+2][N+2][L+2][3]={},a[N+2];
	int n,upperlimit;
	
#define end dasdasdas

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	#define task "main"
	if (fopen(task".inp","r")){
		freopen(task".inp","r",stdin);
		freopen(task".out","w",stdout);
	}
	
	cin>>n>>upperlimit;
	if (n==1) return cout<<1,0;
	for(int i=1;i<=n;++i) cin>>a[i];
	sort(a+1,a+n+1);
	a[n+1]=10000;
	memset(dp,0,sizeof dp);
	dp[0][0][0][0]=1;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=i;++j){
			for(int k=0;k<=upperlimit;++k){
				for(int end=0;end<=2;++end){
					int cost=(2*j-end)*(a[i+1]-a[i]);
					if (cost>k) continue;
					
					// case 1 : build new component
						dp[i][j][k][end]=add(dp[i][j][k][end],dp[i-1][j-1][k-cost][end]);
						
					// case 2 : component with an end point (orient end point)
					if (end)
						dp[i][j][k][end]=add(dp[i][j][k][end],mul(3-end,dp[i-1][j-1][k-cost][end-1]));
					
					// case 3 : append ai in one component without end point
						dp[i][j][k][end]=add(dp[i][j][k][end],mul(2*j-end,dp[i-1][j][k-cost][end]));
						
					// case 4 : append ai in one component that create an end point
						if (end==1){
							dp[i][j][k][end]=add(dp[i][j][k][end],mul(2*j,dp[i-1][j][k-cost][end-1]));
						}
						if (end==2){
							if (i==n) dp[i][j][k][end]=add(dp[i][j][k][end],dp[i-1][j][k-cost][end-1]);
							else 
								if (j>1)
									dp[i][j][k][end]=add(dp[i][j][k][end],mul(j-1,dp[i-1][j][k-cost][end-1]));
						}
					// case 5 : join two existing components
						if (i==n) dp[i][j][k][end]=add(dp[i][j][k][end],dp[i-1][j+1][k-cost][end]);			
						else {
							if (end==2) dp[i][j][k][end]=add(dp[i][j][k][end],mul(mul(j,j-1),dp[i-1][j+1][k-cost][end]));
							if (end==1) dp[i][j][k][end]=add(dp[i][j][k][end],mul(mul(j,j),dp[i-1][j+1][k-cost][end]));
							if (end==0) dp[i][j][k][end]=add(dp[i][j][k][end],mul(mul(j,j+1),dp[i-1][j+1][k-cost][end]));
						}
				}
			}
		}
	}
	
	int ans=0;
	for(int i=0;i<=upperlimit;++i){
		ans=add(ans,dp[n][1][i][2]);
	}
	cout<<ans;
}

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:25:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |                 freopen(task".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:26:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |                 freopen(task".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80