rt,代码如下:
#include <bits/stdc++.h>
#define gc getchar
#define MAXN (100000 + 157)
#define MAXM (200000 + 157)
#define ll long long
using namespace std;
ll n, m1, m2, k1, k2, cnt, ans = -MAXM;
ll a[MAXM];
ll b[MAXN], c[MAXN], sum_b[MAXN], sum_c[MAXN];
bool vis[MAXN];
template <typename T> inline void read(T &x) {
x=0;int f=1;char ch=gc();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc();}
x*=f;
}
struct edge {
ll l, r;
}e1[MAXN], e2[MAXN];
bool inline cmp(edge x, edge y) {
return x.l < y.l;
}
int main() {
// freopen("airport.in", "r", stdin);
// freopen("airport.out", "w", stdout);
read(n), read(m1), read(m2);
for(int i = 1; i <= m1; ++i) {
read(a[++cnt]); e1[i].l = a[cnt];
read(a[++cnt]); e1[i].r = a[cnt];
}
for(int i = 1; i <= m2; ++i) {
read(a[++cnt]); e2[i].l = a[cnt];
read(a[++cnt]); e2[i].r = a[cnt];
}
sort(e1 + 1, e1 + 1 + m1, cmp);
sort(e2 + 1, e2 + 1 + m2, cmp);
ll size = m1, last = 0, tmp = 0, l = 0, r = 0;
k1 = k2 = 1;
while(size > 0) {
l = r = last = 0;
tmp = 0;
for(int i = 1; i <= m1; ++i) {
l = e1[i].l, r = e1[i].r;
if(l < last || vis[i]) continue;
else {
++tmp;
vis[i] = 1;
last = r;
}
}
b[k1] = tmp;
sum_b[k1] = sum_b[k1-1] + b[k1];
size -= tmp;
++k1;
}
--k1;
size = m2, last = l = r = tmp = 0;
memset(vis, 0, sizeof(vis));
while(size > 0) {
tmp = last = l = r = 0;
for(int i = 1; i <= m2; ++i) {
l = e2[i].l, r = e2[i].r;
if(l < last || vis[i]) continue;
else {
++tmp;
vis[i] = 1;
last = r;
}
}
c[k2] = tmp;
sum_c[k2] = sum_c[k2-1] + c[k2];
size -= tmp;
++k2;
}
--k2;
if(k1 + k2 <= n) {
cout << m1 + m2 << endl;
return 0;
}
for(int i = 0; i <= k1; ++i) {
for(int j = 0; j <= k2; ++j) {
if(i + j != n) continue;
ans = max(ans, sum_b[i] + sum_c[j]);
}
}
printf("%lld\n", ans);
return 0;
}
子任务#0 TLE了6个点,子任务#1 全T....
请问有没有救....
求助!!