70pts求调
查看原帖
70pts求调
117665
luoguljz楼主2024/11/9 15:32
#include<bits/stdc++.h>
const int N = 1000005;
typedef long long ll;
using namespace std;
void read(ll &x) {
	char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	x = 0;
	while(isdigit(ch)) {
		x = x*10 + ch - 48;
		ch = getchar();
	}
}
void write(ll x) {
	static int stk[25], top;
	top = 0;
	do {
		stk[++top] = x%10;
		x /= 10;
	}while(x);
	for(; top; -- top) putchar(stk[top] + 48);
}
struct st {
	ll a,b;
}goods[N], tickets[N];
bool cmp(st a, st b) {
	if(a.a != b.a) return a.a > b.a;
	return a.b > b.b;
}
ll n,m;
ll ans;
priority_queue<ll, vector<ll>, greater<ll> > que;
int main() {
	read(n); read(m);
	for(int i = 1; i <= n; ++ i) {
		read(goods[i].a);
		read(goods[i].b);
		ans += goods[i].b;
	}
	sort(goods + 1, goods + n + 1, cmp);
	for(int i = 1; i <= m; ++ i) {
		read(tickets[i].a);
		read(tickets[i].b);
	}
	sort(tickets + 1, tickets + n + 1, cmp);
	for(int i = 1, j = 1; i <= m; ++ i) {
		while(j <= n && goods[j].a >= tickets[i].a) {
			que.push(goods[j].a - goods[j].b);
			++j;
		}
		if(!que.empty() && que.top() < tickets[i].b) {
			ans += que.top() - tickets[i].b;
			que.pop();
			que.push(tickets[i].b);
		}
	}
	write(ans);
	return 0;
}
2024/11/9 15:32
加载中...