Submission #1078290

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <bitset>
#include <utility>
#include <ctime>
#include <cassert>
#include <climits>

using namespace std;

#define TRACE
 
#ifdef TRACE
template<class T, class U>
ostream& operator<<(ostream& out, const pair<T,U>& a){out<<"["<<a.first<<" "<<a.second<<"]";return out;}
template<class T>
ostream& operator<<(ostream& out, const vector<T>& a){out<<"[ ";for(auto &it:a)out<<it<<" ";out<<"]";return out;}
template<class T>
ostream& operator<<(ostream& out, const set<T>& a){out<<"[ ";for(auto &it:a)out<<it<<" ";out<<"]";return out;}
template<class T>
ostream& operator<<(ostream& out, const multiset<T>& a){out<<"[ ";for(auto &it:a)out<<it<<" ";out<<"]";return out;}
template<class T,class U>
ostream& operator<<(ostream& out, const map<T,U>& a){for(auto &it:a)out<<it.first<<" -> "<<it.second<<" | ";return out;}
template<class T,class U>
ostream& operator<<(ostream& out, const multimap<T,U>& a){for(auto &it:a)out<<it.first<<" -> "<<it.second<<" | ";return out;}
#define pra(a,n) cerr<<#a<<" : ";for(int i=0;i<n;++i)cerr<<a[i]<<" ";cerr<<endl;
#define praa(a,n,m) cerr<<#a<<" : "<<endl;for(int i=0;i<n;++i){for(int j=0;j<m;++j)cerr<<a[i][j]<<" ";cerr<<endl;}
#define pr(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
} 
#else
#define pr(...)
#define pra(a,n)
#define praa(a,n,m)
#endif
#define int long long

void Main()	{
	int n, k;
	cin >> n >> k;

	vector<int> a(n + 1), pre(n + 1), kdone(n + 1), positives(n + 1);

	for(int i = 1; i <= n; i++)	{
		cin >> a[i];
		pre[i] = pre[i - 1] + a[i];
		positives[i] = positives[i - 1] + ((a[i] > 0) ? a[i] : 0);
	}

	kdone[k] = max(0LL, pre[k]);

	for(int i = k + 1; i <= n; i++)	{
		kdone[i] = max(positives[i - k] + max(pre[i] - pre[i - k], 0LL), kdone[i - 1] + positives[i] - positives[i - 1]);
	}

	cout << kdone[n] << "\n";
}

#undef int
int main()	{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//freopen("", "r", stdin);
	//freopen("", "w", stdout);
	Main();
}

Submission Info

Judge Result