本文共 2007 字,大约阅读时间需要 6 分钟。
本文出自
/**===================================================== * This is a solution for ACM/ICPC problem * * @source : zoj-3627 Treasure Hunt II * @description : 贪心 * @author : shuangde * @blog : blog.csdn.net/shuangde800 * @email : zengshuangde@gmail.com * Copyright (C) 2013/08/25 12:18 All rights reserved. *======================================================*/#include #include #include #include #include #include #include #include #include #include #define MP make_pair using namespace std; typedef pair PII; typedef long long int64; const double PI = acos(-1.0); const int INF = 0x3f3f3f3f; const int MAXN = 100010; int n, m, t, p; int64 val[MAXN]; int64 sum[MAXN]; int64 func(int64 *sum, int p) { int64 ans = val[p]; for (int r = min(n, p + t); r >= p; --r) { int l = max(1, max(1, r - m)); l = max(p-t, l); int rest_t = t - max(p-l, (r-p)); int l1 = max(1, l - rest_t); int r1 = min(n, r + rest_t); ans = max(ans, max(sum[r]-sum[l1-1], sum[r1]-sum[l-1])); } return ans; } int main( ){ while (~scanf("%d%d", &n, &p)) { sum[0] = 0; for (int i = 1; i <= n; ++i) { cin >> val[i]; sum[i] = sum[i-1] + val[i]; } scanf("%d%d", &m, &t); int64 ans = func(sum, p); for (int i = 1; i <= n/2; ++i) swap(val[i], val[n+1-i]); for (int i = 1; i <= n; ++i) sum[i] = sum[i-1] + val[i]; ans = max(ans, func(sum, n+1-p)); cout << ans << endl; } return 0; }