AC

许诺  •  11天前


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std; int main() {

int N, W;
cin >> N >> W;
const int MAX_X = 1e5 + 5;
vector<int> brightness(MAX_X, 0);

int max_X = 0;
for (int i = 0; i < N; ++i) {
    int Xi, Bi;
    cin >> Xi >> Bi;
    brightness[Xi] += Bi;
    if (Xi > max_X) {
        max_X = Xi;
    }
}
vector<int> prefix_sum(MAX_X + 1, 0);
for (int i = 1; i <= MAX_X; ++i) {
    prefix_sum[i] = prefix_sum[i - 1] + brightness[i];
}

int max_sum = 0;
for (int right = W; right <= max_X; ++right) {
    int left = right - W + 1;
    if (left < 1) {
        left = 1;
    }
    int current_sum = prefix_sum[right] - prefix_sum[left - 1];
    if (current_sum > max_sum) {
        max_sum = current_sum;
    }
}
if (W - 1 >= max_X) {
    max_sum = prefix_sum[max_X];
}
cout << max_sum << endl;
return 0;

}


评论:

请先登录,才能进行评论