比赛 |
EYOI暨SBOI暑假快乐赛2nd |
评测结果 |
AAAAAAAAAAAAAAAAAAAAA |
题目名称 |
最近的母牛获胜 |
最终得分 |
100 |
用户昵称 |
yrtiop |
运行时间 |
3.573 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2022-06-26 09:49:17 |
显示代码纯文本
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
int Ceil(double x) {
return (int)(x - 0.49);
}
const int maxn = 2e5 + 5;
struct node {
int x,y;
node() {
x = y = 0;
}
}a[maxn],s[maxn];
int k,m,n,cnt,f[maxn];
priority_queue<ll> q;
int main() {
freopen("Closest_Cow_Wins.in","r",stdin);
freopen("Closest_Cow_Wins.out","w",stdout);
scanf("%d%d%d",&k,&m,&n);
for(int i = 1;i <= k;++ i)scanf("%d%d",&a[i].x,&a[i].y);
for(int i = 1;i <= m;++ i)scanf("%d",&f[i]);
sort(a + 1 , a + 1 + k , [](node x,node y){return x.x < y.x;});
sort(f + 1 , f + 1 + m);
int L = 1,R = k;
ll tot = 0;
for(;L <= k;++ L) {
if(a[L].x >= f[1])break ;
tot += a[L].y;
}
q.push(tot);
tot = 0;
for(;R;-- R) {
if(a[R].x <= f[m])break ;
tot += a[R].y;
}
q.push(tot);
for(int i = 2,j = L;i <= m;++ i) {
tot = 0;
cnt = 0;
ll ans = 0,sum = 0;
for(;j <= R&&a[j].x == f[i];++ j);
for(;j <= R&&a[j].x < f[i];++ j) {
s[++ cnt] = a[j];
tot += a[j].y;
}
int dist = Ceil((double)(f[i] - f[i - 1]) / 2.0);
int l = 1;
for(int r = 1;r <= cnt;++ r) {
sum += s[r].y;
for(;l <= r&&s[r].x - s[l].x >= dist;++ l)sum -= s[l].y;
ans = max(ans , sum);
}
q.push(ans);
q.push(tot - ans);
for(;j <= R&&a[j].x == f[i];++ j);
}
ll ans = 0;
for(;(n --)&&!q.empty();) {
ans += q.top();
q.pop();
}
printf("%lld",ans);
fclose(stdin);
fclose(stdout);
return 0;
}