AGC 008B - Contiguous Repainting

AGC 008B - Contiguous Repainting

​​ B - Contiguous Repainting Time limit : 2sec / Memory limit : 256MB

Score : 400 points

Problem Statement There are N squares aligned in a row. The i-th square from the left contains an integer ai.

Initially, all the squares are white. Snuke will perform the following operation some number of times:

Select K consecutive squares. Then, paint all of them white, or paint all of them black. Here, the colors of the squares are overwritten. After Snuke finishes performing the operation, the score will be calculated as the sum of the integers contained in the black squares. Find the maximum possible score.

Constraints 1≤N≤105 1≤K≤N ai is an integer. |ai|≤109 Input The input is given from Standard Input in the following format:

N K a1 a2 … aN Output Print the maximum possible score.

Sample Input 1 Copy 5 3 -10 10 -10 10 -10 Sample Output 1 Copy 10 Paint the following squares black: the second, third and fourth squares from the left.

Sample Input 2 Copy 4 2 10 -10 -10 10 Sample Output 2 Copy 20 One possible way to obtain the maximum score is as follows:

Paint the following squares black: the first and second squares from the left. Paint the following squares black: the third and fourth squares from the left. Paint the following squares white: the second and third squares from the left. Sample Input 3 Copy 1 1 -10 Sample Output 3 Copy 0 Sample Input 4 Copy 10 5 5 -4 -5 -8 -4 7 2 -4 0 7 Sample Output 4 Copy 17 题目要求我们每次可以给一个定长（k）的区间去进行黑白覆盖染色 最后求一种方案使得所有的

黑点的权值加起来最大

那么我们首先考虑一个性质 假如我有一个长度为k的 可滑动的窗口 那么窗口两端的所有黑点我一定可以染色 那么问题就转化成 枚举每个窗口 然后求 每个窗口的左端黑点权值是多少 右端黑点的权值是多少 然后分别加上中间一段的权值和 比一下最大最小值即可

#include#include#define N 110000using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x*f;}int a[N],n,k;long long sum1[N],sum2[N];int main(){ freopen("agc.in","r",stdin); n=read();k=read();long long ans=0; for (int i=1;i<=n;++i) { a[i]=read(),sum1[i]=sum1[i-1]+a[i];sum2[i]=sum2[i-1];if (a[i]>0) sum2[i]+=a[i]; }ans=max(ans,sum1[n]); for (int i=1;i<=n-k+1;++i){ long long tmp1=sum2[i-1];long long tmp2=sum2[n]-sum2[i+k-1]; ans=max(ans,tmp1+tmp2);ans=max(ans,tmp1+tmp2+sum1[i+k-1]-sum1[i-1]); } printf("%lld",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。