| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 9333 | Accepted: 3264 |
Description
To avoid unsightly burns while tanning, each of the C (1 ≤ C ≤ 2500) cows must cover her hide with sunscreen when they're at the beach. Cow i has a minimum and maximum SPF rating (1 ≤ minSPF ≤ 1,000; minSPF ≤ maxSPF ≤ 1,000) that will work. If the SPF rating is too low, the cow suffers sunburn; if the SPF rating is too high, the cow doesn't tan at all........
The cows have a picnic basket with L (1 ≤ L ≤ 2500) bottles of sunscreen lotion, each bottle i with an SPF rating SPF (1 ≤ SPF ≤ 1,000). Lotion bottle i can cover cover cows with lotion. A cow may lotion from only one bottle.
What is the maximum number of cows that can protect themselves while tanning given the available lotions?
Input
* Line 1: Two space-separated integers: C and L
* Lines 2..C+1: Line i describes cow i's lotion requires with two integers: minSPF and maxSPF
* Lines C+2..C+L+1: Line i+C+1 describes a sunscreen lotion bottle i with space-separated integers: SPF and cover
Output
A single line with an integer that is the maximum number of cows that can be protected while tanning
Sample Input
3 2
3 10
2 5
1 5
6 2
4 1
Sample Output
2
Source
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <algorithm> const int INF = 0x7fffffff;
const int MAXN = + ; inline void read(int &x)
{
x = ;char ch = getchar(),c = ch;
while(ch < '' || ch > '')c = ch, ch = getchar();
while(ch <= '' && ch >= '')x = x * + ch - '', ch = getchar();
if(c == '-')x = -x;
} int l[MAXN], r[MAXN], cnt[MAXN], point[MAXN], num[MAXN], cntt[MAXN], C, L, ans; bool cmp(int a, int b)
{
return l[a] > l[b];
} bool cmpp(int a, int b)
{
return point[a] > point[b];
} int main()
{
//freopen("data.txt", "r", stdin);
read(C),read(L);
for(register int i = ;i <= C;++ i) read(l[i]), read(r[i]), cnt[i] = i;
for(register int i = ;i <= L;++ i) read(point[i]), read(num[i]), cntt[i] = i;
std::sort(cnt + , cnt + + C, cmp);
std::sort(cntt + , cntt + + L, cmpp);
for(register int i = ;i <= C;++ i)
{
for(register int j = ;j <= L;++ j)
if(num[cntt[j]] > && r[cnt[i]] >= point[cntt[j]] && l[cnt[i]] <= point[cntt[j]])
{
--num[cntt[j]], ++ ans;
break;
}
else if(l[cnt[i]] > point[cntt[j]] ) break;
}
printf("%d", ans);
return ;
}
POJ3614