1. Tạo mảng tiền tố T[i]
2. Với mỗi lần chọn vị trí i (0 -> n) ta cần chọn max(T[j]) trong đoạn (i + l <= j <= i + r)
-> Dùng Segment tree để có thể truy vấn trong O(log(n))
Chú ý: Ngoài Segment tree còn có thể dùng:
- rmq - O(1)
- cây BIT hay Fenwick tree O(log(n))
Code mẫu:
#include <bits/stdc++.h>
using namespace std;
#define inf 1e18
#define ll long long
#define ull unsigned ll
const int mx = 1e5;
int A[mx + 5] = { };
ll T[mx + 5];
ll IT[4*mx + 5];
void build(int id, int l, int r){
if (l == r){
IT[id] = T[l];
return ;
}
int mid = (l + r)/2;
build(id*2, l, mid);
build(id*2 + 1, mid + 1, r);
IT[id] = max(IT[id*2], IT[id*2 + 1]);
}
ll get(int id, int l, int r, int u, int v){
if (v < l || r < u) return -inf;
if (u <= l && r <= v) return IT[id];
int mid = (l + r)/2;
return max(get(id*2, l, mid, u, v), get(id*2 + 1, mid + 1, r, u, v));
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n, l, r;
cin >> n >> l >> r;
for (int i = 1; i <= n; ++i) cin >> A[i];
T[0] = 0;
for (int i = 1; i <= n; ++i) T[i] = T[i - 1] + A[i];
build(1, 1, n);
ll ma = -inf;
for (int i = 0; i <= n - l; ++i) ma = max(ma, get(1, 1, n, l + i, min(n, r + i)) - T[i]);
cout << ma;
}
Sherwin
Created at
0 likes