Solution từ bedao

Nhận xét: Đề bài yêu cầu các phần tử được chọn không là liên tiếp nhưng không quan trọng thứ tự ~(i < j)~ thế nên cách tối ưu để chọn là sắp xếp mảng các phân tử tăng dần ~\rightarrow~ Phần tử lớn nhất luôn nằm ở đầu đoạn chọn và phần tử bé nhất luôn nằm ở cuối đoạn chọn.

Qua đó, duy trì một đoạn có độ dài ~[r-N+1, r]~ rồi lấy ~max(sum(r-N+1, r))~ và đoạn duy trì phải thỏa ~a_r - a_{r-N+1} \leq K~. Để tối ưu cách lấy ~sum(r-N+1,r)~ ta có thể sử dụng ~prefix~ ~sum~ để tính trong ~O(1)~.

Solution được đóng góp từ bạn SPyofgame

Ta chỉ cần sắp xếp lại mảng theo giá trị tăng dần, chọn các đoạn ~[l, r]~ gồm ~N~ người và kiểm tra xem đoạn này có thỏa mãn điều kiện ~max(a[l \dots r]) - min(a[l \dots r]) \leq K \Leftrightarrow a[r]-a[l] \leq K~ hay không.

Có thể tính tổng giá trị của một đoạn từ ~l~ đến ~r~ trong ~O(1)~ bằng cách sử dụng mảng cộng dồn.

Mảng cộng dồn được tính theo công thức : ~sum[i] = sum[i-1]+a[i]~ với ~1 \leq i \leq M~ .

Sau khi đã có mảng cộng dồn, tổng giá trị đoạn từ ~l~ đến ~r~ bằng ~sum[r] - sum[l-1]~.

Vậy bài này có thể làm trong ~O(n\ log n)~, trong đó:

• ~O(n\ log n)~ để sắp xếp

• ~O(n)~ để dựng mảng cộng dồn

• ~O(n)~ để duyệt qua các đoạn và cập nhật kết quả

Code mẫu

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <math.h>
#include <map>
#include <algorithm>
#include <set>
#include <bitset>
#include <queue>
#include <cstring>
#include <stack>
#include <iomanip>
#include <assert.h>

#define _(x) (1LL<<(x))
#define BIT(x,pos) (((x)>>(pos)) & 1LL)
#define turn_all(x) (_(x)-1LL)
#define bitCnt(x) __builtin_popcountll(x)

#define name "test"
#define nameTask ""
#define fastIO ios::sync_with_stdio(false); cin.tie(0);

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

const int N = 1E6;
const ll INF = 1E18;

int a[N+9];
int m,n,k;
ll p[N+9];

int main()
{
    fastIO

    cin>>m>>n>>k;

    for (int i = 1;i <= m; ++i) cin>>a[i];

    sort(a+1,a+1+m);

    for (int i = 1;i <= m; ++i) p[i] = p[i-1] + a[i];

    ll S = -INF;
    for (int i = 1;i <= m; ++i)
        if (i-n+1 >= 1 && a[i] - a[i-n+1] <= k) S = max(S, p[i] - p[i-n]);

    cout<<(S == -INF ? -2 : S);
}