// #pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define rep(i, p, k) for(int i(p); i < (k); ++i) typedef long long int ll; typedef long double ld; template <typename T = int> inline T in() { T x; std::cin >> x; return x; } constexpr int maxn = 3e5 + 3; int tab[maxn]; int sum[maxn]; std::pair <int, int> pyt[maxn]; std::vector <ll> odp[maxn]; std::vector <ll> pdo[maxn]; ll wyn(int a, int b, int n, int K) { int p, k, s; bool ko(0); for(p = 0, k = n-1, s = n/2; !ko; s = (p + k + 1)/2) { if(s < a)p = s; else if(s > b)k = s-1; else ko = 1; } std::cout << a<<' '<<b<<": "; std::cout << p <<' ' <<k<<'\n'; return 0; } void pod(int n, int k, int q) { for(int o(1); o < n; o *= 2)for(int i(0); i < n; i += o) { odp[i].resize(o + k); pdo[i + o-1].resize(o+k); } rep(i, 0, n)rep(j, 1, odp[i].size()) { odp[i][j] = odp[i][j-1]; if(j >= k) odp[i][j] = std::max(odp[i][j], odp[i][j-k] + sum[i + j - k]); } rep(i, 0, n)rep(j, 1, pdo[i].size()) { pdo[i][j] = pdo[i][j-1]; if(j >= k) pdo[i][j] = std::max(pdo[i][j], pdo[i][j-k] + sum[i - j + k]); } rep(i, 0, n) { std::cout << "ODP: "; for(auto j: odp[i])std::cout << j <<' '; std::cout << '\n'; std::cout << "PDO: "; for(auto j: pdo[i])std::cout << j <<' '; std::cout << '\n'; } rep(i, 0, q)std::cout << wyn(pyt[i].first, pyt[i].second, n, k)<<'\n'; } void bod(int n, int k, int q) { rep(i, 0, q)if(odp[pyt[i].first].size() < pyt[i].second - pyt[i].first + 2)odp[pyt[i].first].resize(pyt[i].second - pyt[i].first + 2, 0 ); rep(i, 0, n)rep(j, 1, odp[i].size()) { odp[i][j] = odp[i][j-1]; if(j >= k) odp[i][j] = std::max(odp[i][j], odp[i][j-k] + sum[i + j - k]); } rep(i, 0, q)std::cout << odp[pyt[i].first][pyt[i].second - pyt[i].first + 1]<<'\n'; } int main() { std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios_base::sync_with_stdio(0); int n(in()), k(in()), q(in()); rep(i, 0, n)std::cin >> tab[i]; rep(i, 0, k)sum[0] += tab[i]; rep(i, 1, n-k+1)sum[i] = sum[i-1] - tab[i-1] + tab[i+k-1]; rep(i, 0, q) { std::cin >> pyt[i].first >> pyt[i].second; --pyt[i].first; --pyt[i].second; }bod(n, k, q); 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 | // #pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define rep(i, p, k) for(int i(p); i < (k); ++i) typedef long long int ll; typedef long double ld; template <typename T = int> inline T in() { T x; std::cin >> x; return x; } constexpr int maxn = 3e5 + 3; int tab[maxn]; int sum[maxn]; std::pair <int, int> pyt[maxn]; std::vector <ll> odp[maxn]; std::vector <ll> pdo[maxn]; ll wyn(int a, int b, int n, int K) { int p, k, s; bool ko(0); for(p = 0, k = n-1, s = n/2; !ko; s = (p + k + 1)/2) { if(s < a)p = s; else if(s > b)k = s-1; else ko = 1; } std::cout << a<<' '<<b<<": "; std::cout << p <<' ' <<k<<'\n'; return 0; } void pod(int n, int k, int q) { for(int o(1); o < n; o *= 2)for(int i(0); i < n; i += o) { odp[i].resize(o + k); pdo[i + o-1].resize(o+k); } rep(i, 0, n)rep(j, 1, odp[i].size()) { odp[i][j] = odp[i][j-1]; if(j >= k) odp[i][j] = std::max(odp[i][j], odp[i][j-k] + sum[i + j - k]); } rep(i, 0, n)rep(j, 1, pdo[i].size()) { pdo[i][j] = pdo[i][j-1]; if(j >= k) pdo[i][j] = std::max(pdo[i][j], pdo[i][j-k] + sum[i - j + k]); } rep(i, 0, n) { std::cout << "ODP: "; for(auto j: odp[i])std::cout << j <<' '; std::cout << '\n'; std::cout << "PDO: "; for(auto j: pdo[i])std::cout << j <<' '; std::cout << '\n'; } rep(i, 0, q)std::cout << wyn(pyt[i].first, pyt[i].second, n, k)<<'\n'; } void bod(int n, int k, int q) { rep(i, 0, q)if(odp[pyt[i].first].size() < pyt[i].second - pyt[i].first + 2)odp[pyt[i].first].resize(pyt[i].second - pyt[i].first + 2, 0 ); rep(i, 0, n)rep(j, 1, odp[i].size()) { odp[i][j] = odp[i][j-1]; if(j >= k) odp[i][j] = std::max(odp[i][j], odp[i][j-k] + sum[i + j - k]); } rep(i, 0, q)std::cout << odp[pyt[i].first][pyt[i].second - pyt[i].first + 1]<<'\n'; } int main() { std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios_base::sync_with_stdio(0); int n(in()), k(in()), q(in()); rep(i, 0, n)std::cin >> tab[i]; rep(i, 0, k)sum[0] += tab[i]; rep(i, 1, n-k+1)sum[i] = sum[i-1] - tab[i-1] + tab[i+k-1]; rep(i, 0, q) { std::cin >> pyt[i].first >> pyt[i].second; --pyt[i].first; --pyt[i].second; }bod(n, k, q); return 0; } |