Submission #210047

#	Time	Username	Problem	Language	Result	Execution time	Memory
210047		ld_minh4354	Exhibition (JOI19_ho_t2)	C++14	50 / 100	1058 ms	7136 KiB

joi2019_ho_t2

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second

int n,m,c[100010],i,j,dp[100010],x[100010],l,r,w,ans;
pair<int,int> p[100010];

signed main()
{
    ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m;
	for (i=1;i<n+1;i++) cin>>p[i].se>>p[i].fi;
	for (i=1;i<m+1;i++) cin>>c[i];
	sort(p+1,p+n+1);sort(c+1,c+m+1);
	for (i=1;i<n+1;i++) dp[i]=-1;dp[0]=0;
	for (i=1;i<n+1;i++)
	{
		l=1;r=m;x[i]=m+1;
		while (l<=r)
		{
			w=(l+r)/2;
			if (p[i].se<=c[w])
			{
				x[i]=min(x[i],w);
				r=w-1;
			}
			else l=w+1;
		}
	}
	for (i=1;i<n+1;i++)
	for (j=n-1;j>=0;j--) if (dp[j]!=-1 && x[i]!=m+1)
	{
		if (dp[j+1]==-1) dp[j+1]=max(dp[j]+1,x[i]);else dp[j+1]=min(max(dp[j]+1,x[i]),dp[j+1]);
	}
	ans=0;
	while (dp[ans+1]!=-1 && ans<n && dp[ans+1]<=m) ans++;
	cout<<min(ans,m);
}

Compilation message (stderr)

joi2019_ho_t2.cpp: In function 'int main()':
joi2019_ho_t2.cpp:21:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (i=1;i<n+1;i++) dp[i]=-1;dp[0]=0;
  ^~~
joi2019_ho_t2.cpp:21:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (i=1;i<n+1;i++) dp[i]=-1;dp[0]=0;
                               ^~

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 0 / 50