Submission #96511

#	Time	Username	Problem	Language	Result	Execution time	Memory
96511		Retro3014	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	125 ms	3936 KiB

skyscraper

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;
#define MAX_N 100
#define MAX_L 1000
#define DIV 1000000007
typedef long long ll;

int N, L;
ll dp1[MAX_N+1][MAX_L+1][4], dp2[MAX_N+1][MAX_L+1][4];
vector<ll> v;

int main(){
	scanf("%d%d", &N, &L);
	for(int i=0; i<N; i++){
		ll x;
		scanf("%lld", &x); v.push_back(x);
	}
	if(N==1){
		printf("1");
		return 0;
	}
	dp1[0][0][0] = 1;
	sort(v.begin(), v.end());
	for(int i=0; i<N; i++){
		for(int j=0; j<=N; j++){
			for(int k=0; k<=L; k++){
				for(int t=0; t<4; t++){
					if(dp1[j][k][t]==0)	continue;
					//1-1.
					ll cnt = j+1;
					if(t==1 || t==2)	cnt--;
					if(t==3)	cnt-=2;
					dp2[j+1][k][t] += (cnt * dp1[j][k][t])%DIV;
					dp2[j+1][k][t] = dp2[j+1][k][t] % DIV;
					//1-2.
					if(t==0 || t==2){
						dp2[j+1][k][t+1] += dp1[j][k][t];
						dp2[j+1][k][t+1] = dp2[j+1][k][t+1] % DIV;
					}
					//1-3.
					if(t==0 || t==1){
						dp2[j+1][k][t+2] = (dp2[j+1][k][t+2] + dp1[j][k][t]) %DIV;
					}
					//2-1.
					if(j!=0){
						cnt = j*2;
						if(t==1 || t==2)	cnt--;
						if(t==3)	cnt -= 2;
						dp2[j][k][t] = (dp2[j][k][t] + (cnt * dp1[j][k][t])%DIV)%DIV;
					}
					//2-2.
					if(j!=0 && t!=3 && t!=1){
						dp2[j][k][t+1] = (dp2[j][k][t+1] + dp1[j][k][t])%DIV;
					}
					//2-3.
					if(j!=0 && t!=2 && t!=3){
						dp2[j][k][t+2] = (dp2[j][k][t+2] + dp1[j][k][t])%DIV;
					}
					//3.
					if(j>=2){
						dp2[j-1][k][t] = (dp2[j-1][k][t] + ((ll)j-1) * dp1[j][k][t])%DIV;
					}
				}
			}
		}
		for(int j=0; j<=N; j++){
			for(int k=0; k<=L; k++){
				for(int t=0; t<4; t++)	dp1[j][k][t] = 0;
			}
		}
		for(int j=0; j<=N; j++){
			for(int k=0; k<=L; k++){
				for(int t=0; t<4; t++){
					if(dp2[j][k][t]==0)	continue;
					ll K = 0;
					if(i==N-1){
						K = k;
					}else{
						ll cnt = j*2;
						if(t==1 || t==2)	cnt--;
						if(t==3)	cnt-=2;
						K = (ll)k + cnt*(v[i+1]-v[i]);
					}
					if(K>L){
						dp2[j][k][t] = 0;
					}else{
						dp1[j][K][t] = (dp1[j][K][t]+dp2[j][k][t])%DIV;
						dp2[j][k][t] = 0;
					}
				}
			}
		}
		/*for(int j=0; j<=N; j++){
			for(int k=0; k<=L; k++){
				for(int t=0; t<4; t++){
					if(dp1[j][k][t]!=0)	cout<<i<<' '<<j<<' '<<k<<' '<<t<<' '<<dp1[j][k][t]<<endl;
				}
			}
		}*/
	}
	ll ans = 0;
	for(int k=0; k<=L; k++){
		ans=(ans+dp1[1][k][3])%DIV;
	}
	printf("%lld", ans);
}

Compilation message (stderr)

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, &L);
  ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &x); v.push_back(x);
   ~~~~~^~~~~~~~~~~~

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