Submission #20
ID | Time | User | Problem | Language | Verdict | Time | Memory |
---|---|---|---|---|---|---|---|
20 | Mar/22/2025 15:57 | admin | Forests of Fangorn | cpp | AC | 7 ms | 3584 KB |
Source Code
xxxxxxxxxx
29
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<long long> A(n);
for (int i = 0; i < n; i++){
cin >> A[i];
}
vector<long long> dp(n, LLONG_MIN);
dp[0] = A[0];
deque<int> dq;
dq.push_back(0);
for (int i = 1; i < n; i++){
while (!dq.empty() && dq.front() < i - k)
dq.pop_front();
dp[i] = A[i] + dp[dq.front()];
while (!dq.empty() && dp[dq.back()] <= dp[i])
dq.pop_back();
dq.push_back(i);
}
cout << dp[n - 1];
return 0;
}