# Untitled

unknown
plain_text
2 years ago
3.0 kB
3
Indexable
Never
```#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int tc;
int ret;

int N, S, K;
vector<vector<int>> acorns;

class acorns_comparator
{
public:
bool operator() (const vector<int> &v1, const vector<int> &v2)
{
return v1[0] < v2[0];
}
};

{
cin >> N >> S >> K;

acorns.assign(N, vector<int>(2));

for (int i = 0; i < N; ++i) {
cin >> acorns[i][0] >> acorns[i][1];
}
}

void solve()
{
sort(acorns.begin(), acorns.end(), acorns_comparator());

int left = 0;
int right = N - 1;
int mid;
int left_start, right_start;
vector<int> sums;
ret = 0;

sums.assign(N, 0);
left_start = right_start = -1;

while (left <= right) {
mid = (left + right) / 2;
if (acorns[mid][0] < S) {
left_start = mid;
left = mid + 1;
} else {
right_start = mid;
right = mid - 1;
}
}
if (left_start == -1) {
/*
* all
*/
for (int i = 0; i < N; ++i) {
if (acorns[i][0] - S <= K) {
ret += acorns[i][1];
} else {
break;
}
}
} else if (right_start == -1) {
for (int i = N - 1; i >= 0; i--) {
if (S - acorns[i][0] <= K) {
ret += acorns[i][1];
} else {
break;
}
}
} else {
for (int i = right_start; i < N; i++) {
sums[i] = acorns[i][1] + (i > right_start ? sums[i - 1] : 0);
}
for (int i = left_start; i >= 0; i--) {
sums[i] = acorns[i][1] + (i < left_start ? sums[i + 1] : 0);
}

for (int i = left_start + 1; i >= 0; i--) {
int hld = (i > left_start) ? 0 : (S - acorns[i][0]);
if (hld > K) break;

int ld = hld * 2;
int rd = K - ld;

int lsum = (i > left_start) ? 0 : sums[i];
int rsum = 0;

if (rd > 0) {
left = right_start;
right = N - 1;
while (left <= right) {
mid = (left + right) / 2;
if ((acorns[mid][0] - S <= rd) || ((acorns[mid][0] - S) * 2 + hld <= K)) {
rsum = max(rsum, sums[mid]);
left = mid + 1;
} else {
right = mid - 1;
}
}
}
ret = max(ret, lsum + rsum);
}
}

}

void print_output()
{
cout << "#" << tc << " " << ret << endl;
}

int main(int argc, char **argv)
{
ios_base::sync_with_stdio(false);

int T;
cin >> T;
tc = 1;
while (T) {