Submission #1140118

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

using namespace std;

const int N=101+10,M=1e3+10;
const int mod=1e9+7;
int suf[2*N][2*M],pre[2*N][2*M],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];
	for(int i=0;i<n;i++)cin>>b[i];
	for(int i=1;i<M;i++)compress.push_back(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
			ans+=((pre[i][j]*suf[i][j])%mod);
			if(ans>=mod)ans-=mod;
		}
		for(int j=mpb[i]+1;j<sz;j++)
		{
			ans+=((pre[i][j]*suf[i][j])%mod);
			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...