oj.uz

Submission #960376

# Submission time Handle Problem Language Result Execution time Memory
960376 2024-04-10T10:58:51 Z amirhoseinfar1385 Skyscraper (JOI16_skyscraper) C++17
5 / 100
 6 ms 1372 KB 
#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];
	}
	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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 6 ms 860 KB Output is correct
6 Correct 5 ms 860 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 756 KB Output is correct
9 Correct 6 ms 1116 KB Output is correct
10 Correct 2 ms 604 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 2 ms 1112 KB Output is correct
4 Correct 2 ms 1080 KB Output is correct
5 Correct 2 ms 1116 KB Output is correct
6 Correct 3 ms 1116 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Incorrect 3 ms 1372 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 6 ms 860 KB Output is correct
6 Correct 5 ms 860 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 756 KB Output is correct
9 Correct 6 ms 1116 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 1116 KB Output is correct
12 Correct 2 ms 980 KB Output is correct
13 Correct 2 ms 1112 KB Output is correct
14 Correct 2 ms 1080 KB Output is correct
15 Correct 2 ms 1116 KB Output is correct
16 Correct 3 ms 1116 KB Output is correct
17 Correct 1 ms 860 KB Output is correct
18 Correct 2 ms 1116 KB Output is correct
19 Incorrect 3 ms 1372 KB Output isn't correct
20 Halted 0 ms 0 KB -