Submission #1110745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110745		starchan	Arcade (NOI20_arcade)	C++17	100 / 100	148 ms	28476 KiB

Arcade

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int INF = 1e17;

int LIS(vector<int> v)
{
	int N = v.size();
	vector<int> d(N+2, INF);
	d[0] = -INF;
	for(auto x: v)
	{
		int l = lower_bound(d.begin(), d.end(), x)-d.begin();
		if((d[l-1] < x) && (x < d[l]))
			d[l] = x;
	}
	int s = 0;
	while(d[s] != INF)
		s++;
	return --s;
}

signed main()
{
	fast();
	int M, n; cin >> M >> n;
	vector<in> ab(n);
	for(int i = 0; i < n; i++)
	{
		int t; cin >> t;
		ab[i] = {t, t};
	}
	for(int i = 0; i < n; i++)
	{
		int t; cin >> t;
		ab[i][0]-=t; ab[i][1]+=t;
	}
	sort(ab.begin(), ab.end());
	vector<int> v;
	for(int i = 0; i < n; i++)
		v.pb(ab[n-1-i][1]);
	cout << LIS(v) << "\n";
	return 0;
}	

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 14 / 14
• Subtask 6: 20 / 20
• Subtask 7: 15 / 15