제출 #1140130

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140130		Faisal_Saqib	Flooding Wall (BOI24_wall)	C++20	0 / 100	1 ms	1096 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N=1e3;
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]);
	// for(int i=1;i<=1000;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=1;i<n-1;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;
}

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