#include <bits/stdc++.h> using namespace std; int N, K, Q; vector<long long> skillsSum; struct query { int l; int r; int id; }; bool compareQuery(query &p1, query &p2){ return p1.r < p2.r; } long long *createDP(int end) { auto *result = new long long[end]; for(int i = end - 1; i >= 0; i--) { if(i + K > end) result[i] = 0; else if(i + K == end) { result[i] = max(result[i+1], skillsSum[i + K] - skillsSum[i]); } else { result[i] = max(result[i+1], skillsSum[i + K] - skillsSum[i] + result[i+K]); } } return result; } int main() { std::ios_base::sync_with_stdio(false); cin >> N >> K >> Q; vector<long long> skills; long long sum = 0; skillsSum.push_back(0); for(int i = 0; i < N; i++){ int skill; cin >> skill; skills.push_back(skill); sum += skill; skillsSum.push_back(sum); } vector<query> limits; vector<long long> results; for(int i = 0; i < Q; i++) { int l, r; cin >> l >> r; limits.push_back({l, r, i}); results.push_back(0); } sort(limits.begin(), limits.end(), compareQuery); // for(int i = 0; i < Q; i++){ // cout << limits[i].id <<" " << limits[i].l << " " <<limits[i].r <<endl; // } int prev = -1; long long *DP = nullptr; for(auto & limit : limits) { if(limit.r != prev){ delete [] DP; DP = createDP(limit.r); prev = limit.r; } results[limit.id] = DP[limit.l - 1]; } for(long long result : results){ cout << result << endl; } delete [] DP; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 | #include <bits/stdc++.h> using namespace std; int N, K, Q; vector<long long> skillsSum; struct query { int l; int r; int id; }; bool compareQuery(query &p1, query &p2){ return p1.r < p2.r; } long long *createDP(int end) { auto *result = new long long[end]; for(int i = end - 1; i >= 0; i--) { if(i + K > end) result[i] = 0; else if(i + K == end) { result[i] = max(result[i+1], skillsSum[i + K] - skillsSum[i]); } else { result[i] = max(result[i+1], skillsSum[i + K] - skillsSum[i] + result[i+K]); } } return result; } int main() { std::ios_base::sync_with_stdio(false); cin >> N >> K >> Q; vector<long long> skills; long long sum = 0; skillsSum.push_back(0); for(int i = 0; i < N; i++){ int skill; cin >> skill; skills.push_back(skill); sum += skill; skillsSum.push_back(sum); } vector<query> limits; vector<long long> results; for(int i = 0; i < Q; i++) { int l, r; cin >> l >> r; limits.push_back({l, r, i}); results.push_back(0); } sort(limits.begin(), limits.end(), compareQuery); // for(int i = 0; i < Q; i++){ // cout << limits[i].id <<" " << limits[i].l << " " <<limits[i].r <<endl; // } int prev = -1; long long *DP = nullptr; for(auto & limit : limits) { if(limit.r != prev){ delete [] DP; DP = createDP(limit.r); prev = limit.r; } results[limit.id] = DP[limit.l - 1]; } for(long long result : results){ cout << result << endl; } delete [] DP; return 0; } |