C++14(g++5.4) 解法, 执行用时: 414ms, 内存消耗: 23524K, 提交时间: 2019-05-15 10:21:01

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[2000005];
int main()
{
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	int l = 1, cha = 0;
	ll sum = 0, ans = 0;
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	for (int i = 1; i <= k; i++)
		sum += a[i];
	for (int i = k; i >= 1; i--)
	{
		if (sum < 0)
			break;
		cha = min(sum + 1, (ll)m + a[i]);
		ans += cha;
		sum -= cha;
		a[i] -= cha;
	}
	for (int i = k + 1; i <= n; i++)
	{
		sum += a[i];
		sum -= a[l++];
		if (sum >= 0)
		{
			cha = sum + 1;
			ans += cha;
			sum -= cha;
			a[i] -= cha;
		}
	}
	printf("%lld", ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 402ms, 内存消耗: 23540K, 提交时间: 2019-05-18 14:37:01

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 2e6 + 100;
int a[maxn];

int main() {
	int n, m, k;
	cin >> n >> m >> k;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	ll s = 0, ans = 0;
	for (int i = 0; i < k; ++i) {
		s += a[i];
	}
	for (int i = k; i <= n; ++i) {
		s += a[i] - a[i - k];
		for (int j = i; s >= 0 && j >= 1; --j) {
			ll mi = min(s + 1, 0LL + m + a[j]);
			a[j] -= mi, s -= mi, ans += mi;
		}
	}
	cout << ans << endl;
}