1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
typedef pair<int,int> par;
int n, a[200005], b[200005], pre[200005], nxt[200005], m, ds, dv;
par p[200005];
ll ans;
ll f(ll a, ll b){
if(dv==2) a = a * a;
if(ds==2) b = b * b;
return a - b;
}
int main(){
cin>>n>>m>>ds>>dv;
for(int i=1; i<=n; i++) scanf("%d %d", &p[i].first, &p[i].second);
sort(p+1, p+1+n);
for(int i=1; i<=n; i++){
a[i] = p[i].first;
b[i] = p[i].second;
p[i] = par(b[i], i);
pre[i] = i - 1;
nxt[i] = i + 1;
}
nxt[n] = 0;
sort(p+1, p+1+n);
for(int i=1; i<=n; i++){
ll sum=0;
for(int j=i; j<=i+m-1 && j<=n; j++){
sum += b[j];
ans = max(ans, f(sum, a[j]-a[i]));
}
}
for(int i=1; i<=n; i++){
int x=p[i].second;
int l=x, r=x;
ll sum=b[x];
for(int j=1; j<m; j++){
if(pre[l]){
l = pre[l];
sum += b[l];
}
else if(nxt[r]){
r = nxt[r];
sum += b[r];
}
}
while(l!=nxt[x] && r){
ans = max(ans, f(sum, a[r]-a[l]));
sum -= b[l];
l = nxt[l]; r = nxt[r];
sum += b[r];
}
nxt[pre[x]] = nxt[x];
pre[nxt[x]] = pre[x];
}
cout<<ans<<endl;
return 0;
}
|