WnSOJ
Home
Problems
Jobs
FAQ
API
Swagger UI
ReDoc
Login
Register
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
Theme:
default
darcula
eclipse
Copy Code
#include <iostream> #include <vector> #include <deque> #include <climits> 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; }
cpp