# F2. Animal Observation (hard version)

time limit per test：3 seconds memory limit per test：512 megabytes inputstandard input outputstandard output

The only difference between easy and hard versions is the constraint on k.

Gildong loves observing animals, so he bought two cameras to take videos of wild animals in a forest. The color of one camera is red, and the other one’s color is blue.

Gildong is going to take videos for n days, starting from day 1 to day n. The forest can be divided into m areas, numbered from 1 to m. He’ll use the cameras in the following way:

On every odd day (1-st, 3-rd, 5-th, …), bring the red camera to the forest and record a video for 2 days. On every even day (2-nd, 4-th, 6-th, …), bring the blue camera to the forest and record a video for 2 days. If he starts recording on the n-th day with one of the cameras, the camera records for only one day. Each camera can observe k consecutive areas of the forest. For example, if m=5 and k=3, he can put a camera to observe one of these three ranges of areas for two days: [1,3], [2,4], and [3,5].

Gildong got information about how many animals will be seen in each area on each day. Since he would like to observe as many animals as possible, he wants you to find the best way to place the two cameras for n days. Note that if the two cameras are observing the same area on the same day, the animals observed in that area are counted only once.

Input The first line contains three integers n, m, and k (1≤n≤50, 1≤m≤2⋅10^4^, 1≤k≤m) – the number of days Gildong is going to record, the number of areas of the forest, and the range of the cameras, respectively.

Next n lines contain m integers each. The j-th integer in the i+1-st line is the number of animals that can be seen on the i-th day in the j-th area. Each number of animals is between 0 and 1000, inclusive.

Output Print one integer – the maximum number of animals that can be observed.

input

```4 5 2
0 2 1 1 0
0 0 3 1 2
1 0 4 3 1
3 3 0 0 4```

output

`25`

input

```3 3 1
1 2 3
4 5 6
7 8 9```

output

`31`

input

```3 3 2
1 2 3
4 5 6
7 8 9```

output

`44`

input

```3 3 3
1 2 3
4 5 6
7 8 9```

output

`45`

## 代码

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

int sum[55][20010];//记录前缀和
int a[55][20010];
int tre[80040]; //存值
int laz[80040];//lazy标记
int dp[55][20010];//记录第几题放到第几个位置能拍到最多的数量
void up_down(int x,int l,int r)
{//将 lazy数组的值向下传递
laz[x<<1]+=laz[x];
laz[x<<1|1]+=laz[x];
tre[x<<1]+=laz[x];
tre[x<<1|1]+=laz[x];
laz[x]=0;
return;
}
//进行更新
void up(int x,int l,int r,int ql,int qr,int k)
{
if(ql<=l&&r<=qr)
{
tre[x]+=k;
laz[x]+=k;
return ;
}
int mid=(l+r)>>1;
if(laz[x]) up_down(x,l,r);
if(ql<=mid) up(x<<1,l,mid,ql,qr,k);
if(qr>mid) up(x<<1|1,mid+1,r,ql,qr,k);
tre[x]=max(tre[x<<1],tre[x<<1|1]);
}
//求区间和
int Sum(int xl,int yl,int yr)
{
yl--;
return sum[xl][yr]-sum[xl][yl]+sum[xl+1][yr]-sum[xl+1][yl];
}

int main()
{
ios::sync_with_stdio(0);
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
sum[i][j]=a[i][j]+sum[i][j-1];//记录前缀和
}
}
for(int i=1;i<=m;i++)//更新第一天区间
{
dp[1][i]=Sum(1,i,min(i+k-1,m));//连续的k个位置依次向后移动
}
for(int i=2;i<=n;i++)
{    //每天开始的时候都要初始化
memset(tre,0,sizeof tre);
memset(laz,0,sizeof laz);
for(int j=1;j<=m;j++)//更新线段树的值
{
up(1,1,m,j,j,dp[i-1][j]);
}
for(int j=1;j<=k;j++)
{//减去前一天放在第一个位置和今天放在第一个位置重复拍到的数量
up(1,1,m,1,j,-a[i][j]);
}
for(int j=1;j<=m;j++)
{
dp[i][j]=tre[1]+Sum(i,j,min(j+k-1,m));//前一天能拍到的最大值加上今天在这个位置拍到的数量
up(1,1,m,max(j-k+1,1),j,a[i][j]);//在前天这个位置排到的数量加上这个位置
if(j+k<=m)                        //因为相机放在第二个位置，就拍不到第一个位置了所以第一个位置就不会重复了
{
up(1,1,m,j+1,j+k,-a[i][j+k]);//要放到下个位置的时候，减去如果前一天在下个位置已经排到的
}
}
}
int ans=-1;
for(int i=1;i<=m;i++) ans=max(ans,dp[n][i]);//输出最大值
cout<<ans<<"\n";
return 0;
}```

0 条评论

• ### Dr. Evil Underscores

time limit per test：1 second memory limit per test：256 megabytes inputstandard ...

• ### 2019-2020 ICPC Southeastern European Regional Programming Contest (SEERC 2019)-G.Projection

Everybody knows that you are a TensorFlow fan. Therefore, you’ve been challenged...

• ### 树的直径

这个题刚开始一直不理解，可能是对树的的直径比较陌生吧，可后来看看了看学长给我板子。我去咋这么简单emmm，我真是个智障呀。只要从任意一个节点出发然后找到距离他最...

• ### HDU 1074 Doing Homework(状压DP)

Doing Homework Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32...

• ### PAT 甲级 1068 Find More Coins（0，1背包）

1068. Find More Coins (30) 时间限制 150 ms 内存限制 65536 kB 代码长度限制 16000 B ...

• ### HUST 1354 - Rubiks (DP)

1354 - Rubiks 时间限制：1秒 内存限制：64兆 452 次提交 102 次通过 题目描述 Isun is a genius. Not on...

• ### LeetCode Weekly Contest 38解题思路

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 【PAT甲级】Friend Numbers

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### UESTC 485 Game（康托，BFS）

Today I want to introduce an interesting game to you. Like eight puzzle, it is a...

• ### UESTC 485 Game（康托展开，bfs打表）

Game Time Limit: 4000/2000MS (Java/Others) Memory Limit: 65535/65535KB (Ja...