#include <cstdio> #include <vector> #include <algorithm> const int max_n = 301600; const int sqmax_n = 600; int n, k, q; int a[max_n]; long long pref[max_n]; long long dp[max_n]; long long sdp[max_n]; long long ans[max_n]; long long fdp[61][max_n]; struct Query { int a, b; int index; }; std::vector<Query> groups[sqmax_n]; long long brut(int a, int b) { if (b - a + 1 < k) return 0; for (int i = a + k - 1; i <= b; ++i) { dp[i - a] = dp[i - a - 1]; long long cst = pref[i] - pref[i - k] + dp[i - a - k]; if (cst > dp[i - a]) dp[i - a] = cst; } return dp[b - a]; } int main() { scanf("%d %d %d", &n, &k, &q); pref[0] = 0; for (int i = 1; i <= n; ++i) { scanf("%d", a + i); } for (int i = 1; i <= 2 * sqmax_n; ++i) a[n + i] = 0; n += 2 * sqmax_n; for (int i = 1; i <= n; ++i) { pref[i] = pref[i - 1] + a[i]; } for (int i = 0; i < k; ++i) dp[i] = 0; if (k <= 60 && n >= 10000) { for (int i = 0; i < q; ++i) { int a, b; scanf("%d %d", &a, &b); if (b - a <= 2 * sqmax_n) { ans[i] = brut(a, b); } else { Query q; q.a = a, q.b = b, q.index = i; groups[(a + sqmax_n - 1) / sqmax_n].push_back(q); } } for (int i = 0; i < sqmax_n; ++i) { if (groups[i].size() > 0) { int a = i * sqmax_n; for (int x = 0; x < k; ++x) { for (int y = 0; y <= k + x + 1; ++y) { fdp[x][y + a - 1] = 0; } } for (int j = 0; j < k; ++j) { for (int z = a + k - 1 + j; z <= n; ++z) { fdp[j][z] = fdp[j][z - 1]; long long cst = pref[z] - pref[z - k] + fdp[j][z - k]; if (cst > fdp[j][z]) fdp[j][z] = cst; } } for (int j = 0; j < groups[i].size(); ++j) { sdp[0] = fdp[0][groups[i][j].b]; for (int z = 1; z < k; ++z) { sdp[z] = sdp[z - 1]; long long cst = pref[a - z - 1 + k] - pref[a - z - 1] + fdp[k - z][groups[i][j].b]; if (cst > sdp[z]) sdp[z] = cst; } for (int z = a - k, id = k; z >= groups[i][j].a; --z, ++id) { sdp[id] = sdp[id - 1]; long long cst = sdp[id - k] + pref[z - 1 + k] - pref[z - 1]; if (cst > sdp[id]) sdp[id] = cst; } ans[groups[i][j].index] = sdp[a - groups[i][j].a]; } } } for (int i = 0; i < q; ++i) printf("%lld\n", ans[i]); } else { for (int i = 0; i < q; ++i) { int a, b; scanf("%d %d", &a, &b); printf("%lld\n", brut(a, b)); } } 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 86 87 88 89 90 91 92 93 94 95 96 97 | #include <cstdio> #include <vector> #include <algorithm> const int max_n = 301600; const int sqmax_n = 600; int n, k, q; int a[max_n]; long long pref[max_n]; long long dp[max_n]; long long sdp[max_n]; long long ans[max_n]; long long fdp[61][max_n]; struct Query { int a, b; int index; }; std::vector<Query> groups[sqmax_n]; long long brut(int a, int b) { if (b - a + 1 < k) return 0; for (int i = a + k - 1; i <= b; ++i) { dp[i - a] = dp[i - a - 1]; long long cst = pref[i] - pref[i - k] + dp[i - a - k]; if (cst > dp[i - a]) dp[i - a] = cst; } return dp[b - a]; } int main() { scanf("%d %d %d", &n, &k, &q); pref[0] = 0; for (int i = 1; i <= n; ++i) { scanf("%d", a + i); } for (int i = 1; i <= 2 * sqmax_n; ++i) a[n + i] = 0; n += 2 * sqmax_n; for (int i = 1; i <= n; ++i) { pref[i] = pref[i - 1] + a[i]; } for (int i = 0; i < k; ++i) dp[i] = 0; if (k <= 60 && n >= 10000) { for (int i = 0; i < q; ++i) { int a, b; scanf("%d %d", &a, &b); if (b - a <= 2 * sqmax_n) { ans[i] = brut(a, b); } else { Query q; q.a = a, q.b = b, q.index = i; groups[(a + sqmax_n - 1) / sqmax_n].push_back(q); } } for (int i = 0; i < sqmax_n; ++i) { if (groups[i].size() > 0) { int a = i * sqmax_n; for (int x = 0; x < k; ++x) { for (int y = 0; y <= k + x + 1; ++y) { fdp[x][y + a - 1] = 0; } } for (int j = 0; j < k; ++j) { for (int z = a + k - 1 + j; z <= n; ++z) { fdp[j][z] = fdp[j][z - 1]; long long cst = pref[z] - pref[z - k] + fdp[j][z - k]; if (cst > fdp[j][z]) fdp[j][z] = cst; } } for (int j = 0; j < groups[i].size(); ++j) { sdp[0] = fdp[0][groups[i][j].b]; for (int z = 1; z < k; ++z) { sdp[z] = sdp[z - 1]; long long cst = pref[a - z - 1 + k] - pref[a - z - 1] + fdp[k - z][groups[i][j].b]; if (cst > sdp[z]) sdp[z] = cst; } for (int z = a - k, id = k; z >= groups[i][j].a; --z, ++id) { sdp[id] = sdp[id - 1]; long long cst = sdp[id - k] + pref[z - 1 + k] - pref[z - 1]; if (cst > sdp[id]) sdp[id] = cst; } ans[groups[i][j].index] = sdp[a - groups[i][j].a]; } } } for (int i = 0; i < q; ++i) printf("%lld\n", ans[i]); } else { for (int i = 0; i < q; ++i) { int a, b; scanf("%d %d", &a, &b); printf("%lld\n", brut(a, b)); } } return 0; } |