枚举bi,找到大于bi的所有ai
#include <bits/stdc++.h>//代码来源某位不知名大佬
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--) {
ll n, m; cin >> n >> m;
vector<pll> arr(m);
for (int i = 0; i < m; ++i) cin >> arr[i].first >> arr[i].second;
sort(arr.begin(), arr.end());
vector<ll> front(m + 1), prefix(m + 1);
for (int i = 0; i < m; ++i) {
front[i + 1] = arr[i].first;
prefix[i + 1] = prefix[i] + arr[i].first;
}
ll ans = 0;
for (int i = 0; i < m; ++i) {
int ind = upper_bound(front.begin(), front.end(), arr[i].second) - front.begin() - 1;
ind = max(ind, (int)(m - n + 1));
ll res = prefix.back() - prefix[ind];
ll rem = n - (m - ind);
res += (i >= ind? arr[i].second * rem: arr[i].first + arr[i].second * (rem - 1));
ans = max(ans, res);
}
ans = max(ans, prefix.back() - prefix[max(0LL, m - n)]);
cout << ans << '\n';
}
return 0;
}
链接: Codeforces Round #657 (Div. 2) C题.
本文地址:https://blog.csdn.net/Peiris_/article/details/107497211
如对本文有疑问, 点击进行留言回复!!
Codeforces Round #657 (Div. 2) C题
hdu2222 Keywords Search(ac自动机模板-kuangbin)
IOS开发控件视图day08:监听文本框状态设置按钮状态不可点击且变灰
网友评论