Submission #1140084

#TimeUsernameProblemLanguageResultExecution timeMemory
1140084Faisal_SaqibFlooding Wall (BOI24_wall)C++20
0 / 100
0 ms580 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N=101;
const int mod=1e9+7;
int suf[N][2*N],pre[N][2*N],a[N],b[N],mpa[N],mpb[N];
vector<int> compress;
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i],compress.push_back(a[i]);
	for(int i=0;i<n;i++)cin>>b[i],compress.push_back(b[i]);
	
	sort(begin(compress),end(compress));
	compress.resize(unique(begin(compress),end(compress))-begin(compress));
	
	for(int i=0;i<n;i++)mpa[i]=lower_bound(begin(compress),end(compress),a[i])-begin(compress);
	for(int i=0;i<n;i++)mpb[i]=lower_bound(begin(compress),end(compress),b[i])-begin(compress);

	int sz=compress.size();

	pre[0][0]=1;

	for(int i=0;i<n;i++)
	{
		for(int j=0;j<sz;j++)
		{
			pre[i+1][max(j,mpa[i])]+=pre[i][j];
			if(pre[i+1][max(j,mpa[i])]>=mod)pre[i+1][max(j,mpa[i])]-=mod;

			pre[i+1][max(j,mpb[i])]+=pre[i][j];			
			if(pre[i+1][max(j,mpb[i])]>=mod)pre[i+1][max(j,mpb[i])]-=mod;
		}
	}

	suf[n-1][0]=1;

	for(int i=n-1;i>0;i--)
	{
		for(int j=0;j<sz;j++)
		{
			suf[i-1][max(j,mpa[i])]+=suf[i][j];
			if(suf[i-1][max(j,mpa[i])]>=mod)suf[i-1][max(j,mpa[i])]-=mod;

			suf[i-1][max(j,mpb[i])]+=suf[i][j];			
			if(suf[i-1][max(j,mpb[i])]>=mod)suf[i-1][max(j,mpb[i])]-=mod;
		}		
	}

	int ans=0;
	for(int i=0;i<n;i++)
	{
		// use pre[i]
		for(int j=sz-2;j>=0;j--)
		{
			pre[i][j]+=pre[i][j+1];
			suf[i][j]+=suf[i][j+1];
		}
		for(int j=mpa[i]+1;j<sz;j++)
		{
			// if for each (i,h) number of ways such that height of i is atleast h
			// 
			int cur=((pre[i][j]*suf[i][j])%mod);
			if(j>(mpa[i]+1))
			{
				int len=(compress[j]-compress[j-1]);
				cur=(cur*len)%mod;
			}
			ans+=(cur);
			if(ans>=mod)ans-=mod;
		}
		for(int j=mpb[i]+1;j<sz;j++)
		{
			int cur=((pre[i][j]*suf[i][j])%mod);
			// if for each (i,h) number of ways such that height of i is atleast h
			if(j>(mpb[i]+1))
			{
				int len=(compress[j]-compress[j-1]);
				cur=(cur*len)%mod;
			}
			ans+=(cur);
			if(ans>=mod)ans-=mod;
		}
		// way to make height >=j on prefix i
	}
	cout<<ans<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...