Submission #960377

#	Time	Username	Problem	Language	Result	Execution time	Memory
960377		amirhoseinfar1385	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	974 ms	98860 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
const int maxn=100+10,maxl=1000+10,mod=1e9+7;
int dp[maxn][maxn][maxl][4],l,n;
vector<int>all;
void vorod(){
	cin>>n>>l;
	all.resize(n);
	for(int i=0;i<n;i++){
		cin>>all[i];
	}
	sort(all.begin(),all.end());
	int z=all.back();
	all.push_back(z);
}

void add(int a,int b,int c,int d,int aa,int bb,int cc,int dd,int w){
//	if(aa==0&&dd==3&&dp[aa][bb][cc][dd]!=0){
//		cout<<"wtf"<<endl;
//	}
	long long e=1ll*dp[aa][bb][cc][dd]*w%mod;
	dp[a][b][c][d]+=e;
	dp[a][b][c][d]%=mod;
}

void upd(int ind,int ted,int dis,int tar){
//	cout<<ind<<" "<<ted<<" "<<dis<<" "<<tar<<" "<<dp[ind][ted][dis][tar]<<" "<<all[ind+2]-all[ind+1]<<endl;
	long long val=dp[ind][ted][dis][tar];
	long long ezaf=all[ind+2]-all[ind+1],te=ted*2+__builtin_popcount(tar);
	if(ted>0){
		//vas00;
		if(dis+ezaf*(te+2)<=l){
			add(ind+1,ted+1,dis+ezaf*(te+2),tar,ind,ted,dis,tar,ted);
		}

		//vas10;
		if(dis+ezaf*(te)<=l){
			add(ind+1,ted,dis+ezaf*(te),tar,ind,ted,dis,tar,ted);
		}

		//vas01;
		if(dis+ezaf*(te)<=l){
			add(ind+1,ted,dis+ezaf*(te),tar,ind,ted,dis,tar,ted);
		}

		//vas11;
		if(dis+ezaf*(te-2)<=l){
			add(ind+1,ted-1,dis+ezaf*(te-2),tar,ind,ted,dis,tar,ted);
		}

	}
	if(tar&1){
		//vas00;
		if(dis+ezaf*(te+2)<=l){
			add(ind+1,ted+1,dis+ezaf*(te+2),tar,ind,ted,dis,tar,1);
		}

		//vas10;
		if(dis+ezaf*(te)<=l){
			add(ind+1,ted,dis+ezaf*(te),tar,ind,ted,dis,tar,1);
		}

		//vas01;
		if(dis+ezaf*(te+1)<=l){
			add(ind+1,ted+1,dis+ezaf*(te+1),tar^1,ind,ted,dis,tar,1);
		}

		//vas11;
		if(dis+ezaf*(te-1)<=l){
			add(ind+1,ted,dis+ezaf*(te-1),tar^1,ind,ted,dis,tar,1);
		}
	}
	if(tar&2){
		//vas00;
		if(dis+ezaf*(te+2)<=l){
			add(ind+1,ted+1,dis+ezaf*(te+2),tar,ind,ted,dis,tar,1);
		}

		//vas10;
		if(dis+ezaf*(te+1)<=l){
			add(ind+1,ted+1,dis+ezaf*(te+1),tar^2,ind,ted,dis,tar,1);
		}

		//vas01;
		if(dis+ezaf*(te)<=l){
			add(ind+1,ted,dis+ezaf*(te),tar,ind,ted,dis,tar,1);
		}

		//vas11;
		if(dis+ezaf*(te-1)<=l){
			add(ind+1,ted,dis+ezaf*(te-1),tar^2,ind,ted,dis,tar,1);
		}
	}
}

void pre(){
	dp[0][0][0][0]=1;
	dp[0][0][all[1]-all[0]][1]=1;
	dp[0][0][all[1]-all[0]][2]=1;
	dp[0][0][2*(all[1]-all[0])][3]=1;
	for(int i=1;i<n;i++){
		for(int j=0;j<n;j++){
			for(int h=0;h<=l;h++){
				for(int z=0;z<4;z++){
					upd(i-1,j,h,z);
				}
			}
		}
	}
}

void khor(){
	long long mainres=0;
	for(int i=0;i<=l;i++){
		mainres+=dp[n-1][0][i][0];
	}
	mainres%=mod;
	cout<<mainres<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	freopen("inp.txt","r",stdin);
	vorod();
	//cout<<"salam"<<endl;
	pre();
	khor();
}

Compilation message (stderr)

skyscraper.cpp: In function 'void upd(int, int, int, int)':
skyscraper.cpp:28:12: warning: unused variable 'val' [-Wunused-variable]
   28 |  long long val=dp[ind][ted][dis][tar];
      |            ^~~

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