잔디 깎기-단조로운 대기열 최적화 DP 기초

최근에 DP를 복습하고 있어서 단조로운 대기열 최적화 DP를 쓰려고 합니다.사실 단조로운 대기열로 DP를 최적화하는 방법은 제 블로그에 있는데 제가 다 까먹었어요.
그러니까 복습이지?
제목은 1년 전 마을에서 최고의 잔디밭을 이긴 후 팜존이 게으르게 변해 잔디를 깎은 적이 없다는 것이다.이제 새로운 최고의 잔디밭 경기가 시작됐고, 팜존은 다시 우승을 노린다.
그러나 팜존의 잔디밭은 매우 지저분하기 때문에 팜존은 그의 젖소만 이 일을 완성할 수 있다.팜존에는 N(1<=N <=100000)만 줄지어 늘어선 젖소가 있는데, 번호는 1...N이다.젖소 i의 효율은 Ei(0 <= E_i <= 1,000,000,000).
가까운 젖소들은 익숙하기 때문에 팜존이 K마리를 넘는 연속 젖소를 배치한다면 이 젖소들은 파업해서 파티를 열 것이다.따라서 현재 팜존은 FJ가 얻을 수 있는 최대 효율을 계산하는 데 도움을 필요로 하고, 이 방안에는 K마리를 넘는 젖소가 연속적으로 없다.
입력 출력 형식: 첫 줄: 공백으로 구분된 두 정수 N 및 K
두 번째 줄에서 N+1 줄: i+1 줄에는 정수 Ei
출력 형식: 첫 번째 줄: Farm John이 얻을 수 있는 최대 효율 값을 나타내는 값.
입력 출력 예제 입력 예제 #1:5 2 1 2 3 4 5 출력 예제 #1:12
s u m i sum으로{i}sumi는 접두사와 를 나타내므로 상태 이동 방정식은 다음과 같습니다. fi, 1 = m a x(s u m i -3. s u m j + f j, 0) f{i,1}=max(sum_{i}-sum{j}+f_{j,0}) fi,1​=max(sumi​−sumj+fj,0​) f i , 0 = m a x ( f i − 1 , 0 , f i − 1 , 1 ) f_{i,0}=max(f_{i-1,0},f_{i-1,1}) fi,0​=max(fi−1,0​,fi−1,1​)
하지만 직접 폭력으로 jjj를 매거하면 우리는 시간을 초과할 것이다.첫 번째 형식 관찰: fi, 1 = m a x(s u m i -3. s u m j + f j, 0) f{i,1}=max(sum {i}-sum{j}+f {j,0})fi,1=max(sumi-4-sumj+fj,0)의 이동에 대해 우리는 가장 큰 - sumj+fj,0-sum{j}+f{j, 0} -3 sumj+fj, 0, 그래서 그것을 -3 s u m j + f j, 0 -sum {j} + f{j, 0} -3. sumj+fj, 0은 단조로운 대기열의 요소로 그 증가성을 유지하면 된다.

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define N 100010
#define LL long long
#define inf 0x7f7f7f7f
#define reg register

struct fuck {
    LL L,M;
    fuck () {};
    fuck (LL L1,LL M1) {L=L1; M=M1;}
};

LL n,m,A[N],f[N][2],ans,sum[N];
deque q;

int main() {
    cin>>n>>m;
    for(reg int i=1;i<=n;i++) scanf("%lld",&A[i]);
    for(int i=1;i<=n;i++ ) sum[i]=sum[i-1]+A[i];
    q.push_front( fuck(0,0) );
    for(reg LL i=1,pos;i<=n;i++) {
        f[i][1]=q.front().L+sum[i];
        f[i][0]=max(f[i-1][0],f[i-1][1]);
        while(!q.empty() && q.front().M