Submission #1140013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140013		Faisal_Saqib	Fire (BOI24_fire)	C++20	14 / 100	295 ms	108256 KiB

Main

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

using namespace std;

const int N=302;

int dp[N][N][N];
int s[N],e[N],mpe[N],mps[N],ord[N];
vector<int> s_p;
bool funot(int a,int b)
{
	return (s[a]<s[b] or (s[a]==s[b] and e[a]<e[b]));
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		ord[i]=i;
		cin>>s[i]>>e[i];
		s_p.push_back(s[i]);
		s_p.push_back(e[i]);
	}
	sort(ord,ord+n,funot);
	s_p.push_back(0);
	s_p.push_back(m-1);
	if(n<=500)
	{
		sort(begin(s_p),end(s_p));
		s_p.resize(unique(begin(s_p),end(s_p))-begin(s_p));
		int sz=s_p.size();
		for(int i=0;i<=n;i++)
		{
			if(i<n)
			{
				mps[i]=lower_bound(begin(s_p),end(s_p),s[i])-begin(s_p);
				mpe[i]=lower_bound(begin(s_p),end(s_p),e[i])-begin(s_p);
			}
			for(int j=0;j<sz;j++)
			{
				for(int k=0;k<sz;k++)
				{
					dp[i][j][k]=n+1e5;
				}
			}
		}
		int ans=n+1e5;
		for(int iads=0;iads<n;iads++)
		{
			int i=ord[iads];
			for(int l=sz-1;l>=1;l--)
			{
				for(int j=0;j<sz;j++)
				{
					int k=j+l-1;
					if(k<sz)
					{
						if((j-1)>=0)
							dp[iads][j][k]=min(dp[iads][j][k],dp[iads][j-1][k]);
						if((k+1)<sz)
							dp[iads][j][k]=min(dp[iads][j][k],dp[iads][j][k+1]);
						if((k+1)<sz and (j-1)>=0)
							dp[iads][j][k]=min(dp[iads][j][k],dp[iads][j-1][k+1]);
					}
				}
			}
			for(int j=0;j<sz;j++)
				for(int k=j;k<sz;k++)
					dp[iads+1][j][k]=min(dp[iads+1][j][k],dp[iads][j][k]);
			if(s[i]<=e[i])
			{
				for(int j=0;j<sz;j++)
				{
					for(int k=j;k<sz;k++)
					{
						int l=s_p[j],r=s_p[k];
						if(s[i]<=l and r<=e[i])
						{
							// can be covered using only current meaning i
							dp[iads+1][j][k]=min(dp[iads+1][j][k],1);
						}
						if(s[i]<=r)
							dp[iads+1][j][max(k,mpe[i])]=min(dp[iads+1][j][max(k,mpe[i])],dp[iads][j][k]+1);
					}
				}
			}
			else
			{
				for(int j=0;j<sz;j++)
				{
					for(int k=j;k<sz;k++)
					{
						int l=s_p[j],r=s_p[k];
						if(s[i]<=l)
						{
							// simply it is two segments [0,e[i]] and [s[i],m]
							ans=min(ans,dp[iads][mpe[i]][mps[i]]+1);
							// 
							// can be covered using only current meaning i
							dp[iads+1][j][k]=min(dp[iads+1][j][k],1);
						}
						if(r<=e[i])
							dp[iads+1][j][k]=min(dp[iads+1][j][k],1);							
						if(s[i]<=r)
						{
							// cover [l,r]
							// we can do [r,m]
							// [l,m]
							// s[i] to m
							dp[iads+1][j][sz-1]=min(dp[iads+1][j][sz-1],dp[iads][j][k]+1);
						}
						if(l<=e[i])
						{
							// cover [l,r]
							// we can do [0,l]
							// [0,r]
							dp[iads+1][0][k]=min(dp[iads+1][0][k],dp[iads][j][k]+1);
						}
						if(l<=e[i] and s[i]<=r)
						{
							dp[iads+1][0][sz-1]=min(dp[iads+1][0][sz-1],dp[iads][j][k]+1);
							ans=min(ans,dp[iads][j][k]+1);
						}
					}
				}
			}
		}
		ans=min(ans,dp[n][0][sz-1]);
		if(ans>n)
			ans=-1;
		cout<<ans<<endl;
	}
	else
	{
		cout<<-1<<endl;
	}
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 17
• Subtask 3: 0 / 9
• Subtask 4: 0 / 13
• Subtask 5: 0 / 21
• Subtask 6: 0 / 26