Submission #1140089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140089		Faisal_Saqib	Flooding Wall (BOI24_wall)	C++20	0 / 100	2 ms	1864 KiB

Main

#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;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 17
• Subtask 3: 0 / 19
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 30