Submission #210047

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
210047	2020-03-16T13:09:49 Z	ld_minh4354	Exhibition (JOI19_ho_t2)	C++14	50 / 100	1000 ms	7136 KB

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

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	380 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	4 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	4 ms	376 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	5 ms	376 KB	Output is correct
12	Correct	5 ms	376 KB	Output is correct
13	Correct	5 ms	376 KB	Output is correct
14	Correct	5 ms	376 KB	Output is correct
15	Correct	5 ms	376 KB	Output is correct
16	Correct	5 ms	376 KB	Output is correct
17	Correct	5 ms	376 KB	Output is correct
18	Correct	5 ms	376 KB	Output is correct
19	Correct	5 ms	376 KB	Output is correct

Subtask #2
40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	380 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	4 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	4 ms	376 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	5 ms	376 KB	Output is correct
12	Correct	5 ms	376 KB	Output is correct
13	Correct	5 ms	376 KB	Output is correct
14	Correct	5 ms	376 KB	Output is correct
15	Correct	5 ms	376 KB	Output is correct
16	Correct	5 ms	376 KB	Output is correct
17	Correct	5 ms	376 KB	Output is correct
18	Correct	5 ms	376 KB	Output is correct
19	Correct	5 ms	376 KB	Output is correct
20	Correct	7 ms	380 KB	Output is correct
21	Correct	7 ms	376 KB	Output is correct
22	Correct	7 ms	376 KB	Output is correct
23	Correct	7 ms	376 KB	Output is correct
24	Correct	7 ms	376 KB	Output is correct
25	Correct	7 ms	376 KB	Output is correct
26	Correct	7 ms	380 KB	Output is correct
27	Correct	7 ms	376 KB	Output is correct
28	Correct	7 ms	376 KB	Output is correct
29	Correct	7 ms	376 KB	Output is correct
30	Correct	7 ms	376 KB	Output is correct
31	Correct	7 ms	504 KB	Output is correct
32	Correct	7 ms	376 KB	Output is correct
33	Correct	5 ms	376 KB	Output is correct
34	Correct	7 ms	376 KB	Output is correct
35	Correct	5 ms	376 KB	Output is correct
36	Correct	7 ms	504 KB	Output is correct
37	Correct	7 ms	376 KB	Output is correct

Subtask #3
0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	380 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	4 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	4 ms	376 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	5 ms	376 KB	Output is correct
12	Correct	5 ms	376 KB	Output is correct
13	Correct	5 ms	376 KB	Output is correct
14	Correct	5 ms	376 KB	Output is correct
15	Correct	5 ms	376 KB	Output is correct
16	Correct	5 ms	376 KB	Output is correct
17	Correct	5 ms	376 KB	Output is correct
18	Correct	5 ms	376 KB	Output is correct
19	Correct	5 ms	376 KB	Output is correct
20	Correct	7 ms	380 KB	Output is correct
21	Correct	7 ms	376 KB	Output is correct
22	Correct	7 ms	376 KB	Output is correct
23	Correct	7 ms	376 KB	Output is correct
24	Correct	7 ms	376 KB	Output is correct
25	Correct	7 ms	376 KB	Output is correct
26	Correct	7 ms	380 KB	Output is correct
27	Correct	7 ms	376 KB	Output is correct
28	Correct	7 ms	376 KB	Output is correct
29	Correct	7 ms	376 KB	Output is correct
30	Correct	7 ms	376 KB	Output is correct
31	Correct	7 ms	504 KB	Output is correct
32	Correct	7 ms	376 KB	Output is correct
33	Correct	5 ms	376 KB	Output is correct
34	Correct	7 ms	376 KB	Output is correct
35	Correct	5 ms	376 KB	Output is correct
36	Correct	7 ms	504 KB	Output is correct
37	Correct	7 ms	376 KB	Output is correct
38	Execution timed out	1058 ms	7136 KB	Time limit exceeded
39	Halted	0 ms	0 KB	-

Submission #210047

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 40.0 / 40.0

Subtask #3 0 / 50.0

Subtask #1
10.0 / 10.0

Subtask #2
40.0 / 40.0

Subtask #3
0 / 50.0