Subtask 1 (11 คะแนน) $N,M\leq300$ และ $S=0$

สำหรับปัญหาย่อยนี้จะสังเกตได้ว่าสถานีไหนก็ตามที่มีคนอยู่ทั้งสองฝั่งเราจะเลือกจอดแล้วรับคนขึ้นรถไฟทั้งหมด แต่หากสถานีไหนมีซอมบี้อยู่ทั้งสองฝั่งเราจะเลือกข้ามสถานีนั้น ส่วนสถานีที่เหลือเราสามารถหาวิธีการรับคนให้ได้มากที่สุดโดยที่ประตูไม่พังได้ด้วยการแก้ปัญหาแบบ Dynamic Programming โดยใช้วิธีการ Knapsack 0/1 แต่เนื่องจากประตูมีสองข้าง จึงต้องเพิ่มมิติที่ 3 ให้กับ dp ของเรา โดยเราจะนิยาม ให้ $dp[i][j][k]$ คือ จำนวนคนที่รับได้มากที่สุดเมื่อไปถึงสถานีที่ $i$ โดยประตูข้างซ้ายและขวาโดนโจมตีไปแล้ว $j,k$ หน่วยตามลำดับ

• เมื่อฝั่งซ้ายเป็น คน และฝั่งขวาเป็น ซอมบี้

$dp[i][j][k]=\max(dp[i-1][j][k],dp[i-1][j][k+R[i]]+L[i])$

• เมื่อฝั่งซ้ายเป็น ซอมบี้ และฝั่งขวาเป็น คน

$dp[i][j][k]=\max(dp[i-1][j][k],dp[i-1][j+L[i]][k]+R[i])$

• เมื่อทั้งสองฝั่งเป็นคน

$dp[i][j][k]=dp[i-1][j][k]+L[i]+R[i]$

• เมื่อทั้งสองฝั่งเป็นซอมบี้

$dp[i][j][k]=dp[i-1][j][k]$

เนื่องจากยังไม่มีการสลับประตูเกิดขึ้น $(S=0)$ คำตอบของเราจึงเป็น $dp[N][M][M]$ ได้เลย

Time Complexity: $\mathcal{O}(NM^2)$

Subtask 2 (15 คะแนน) $N,M\leq300$

ปัญหาย่อยนี้แนวคิดยังคงเหมือนกับปัญหาย่อยแรก เพียงแต่เราต้องเพิ่มมิติที่สี่ให้กับ dp ตัวเดิมของเรา เนื่องจากสามารถเลือกสลับประตูได้ โดยจะนิยามให้ $dp[i][j][k][s]$ คือ จำนวนคนที่รับได้มากที่สุดเมื่อไปถึงสถานีที่ $i$ โดยประตูข้างซ้ายและขวาโดนโจมตีไปแล้ว $j,k$ หน่วย ตามลำดับ และสลับประตูไปแล้ว s ครั้ง

• เมื่อเกิดการสลับประตูขึ้น

$dp[i][j][k][1]=\max(dp[i][j][k][1],dp[i][k][j][0])$

เนื่องจากครั้งนี้อาจมีการสลับประตูเกิดขึ้น $(S=1)$ คำตอบของเราจึงเป็น $\max(dp[N][M][M][0],dp[N][M][M][1])$

Time Complexity: $\mathcal{O}(NM^2)$

Subtask 3 (19 คะแนน) ฝั่งซ้ายของทุกสถานีจะไม่มีซอมบี้

ปัญหาย่อยนี้ทำให้เราสังเกตได้ว่าจริงๆแล้วเงื่อนไขการรับคนขึ้นรถไฟของประตูทั้งสองข้างไม่ได้มีความเกี่ยวข้องกันเลย สำหรับการเก็บคะแนนของปัญหาย่อยนี้ เราสามารถนิยามให้ $dp[i][j][s]$ คือ จำนวนคนที่รับได้มากที่สุดเมื่อไปถึงสถานีที่ $i$ โดยประตูข้างขวาโดนโจมตีไปแล้ว $j$ หน่วย และสลับประตูไปแล้ว $s$ ครั้ง

ข้อสังเกต : ประตูฝั่งซ้ายจะไม่ถูกโจมตีเลยซักครั้งก่อนการสลับประตู ฉะนั้นการสลับประตูก็เปรียบเสมือนได้รับค่าความแข็งแรงของประตูกลับไปเป็น M อีกครั้ง เพราะประตูอีกข้างที่นำมาแทนที่ยังไม่เคยถูกโจมตี

• เมื่อฝั่งซ้ายเป็น คน และฝั่งขวาเป็น ซอมบี้

$dp[i][j][s]=\max(dp[i-1][j][s],dp[i-1][j+R[i]][s]+L[i])$

• เมื่อทั้งสองฝั่งเป็นคน

$dp[i][j][s]=dp[i-1][j][s]+L[i]+R[i]$

• เมื่อเกิดการสลับประตูขึ้น

$dp[i][j][1]=\max(dp[i][j][1],dp[i][M][0])$

คำตอบ : $\max(dp[N][M][0],dp[N][M][1])$

Time Complexity: $\mathcal{O}(NM)$

Subtask 4 (23 คะแนน) $S=0$

เราสามารถนำข้อสังเกตของปัญหาย่อยก่อนหน้ามาใช้แก้ปัญหาย่อยนี้ได โดยจะทำการคิด Knapsack 0/1 แยกฝั่งแล้วค่อยนำคำตอบที่ได้จากฝั่งซ้ายและฝั่งขวามารวมกันตอนจบ โดยเราสามารถนิยามให้ $dp[i][j][0]$ คือ จำนวนคนที่รับได้มากที่สุดเมื่อไปถึงสถานีที่ $i$ โดยประตูข้างขวาโดนโจมตีไปแล้ว $j$ หน่วย และ $dp[i][j][1]$ คือ จำนวนคนที่รับได้มากที่สุดเมื่อไปถึงสถานีที่ $i$ โดยประตูข้างซ้ายโดนโจมตีไปแล้ว $j$ หน่วย

ข้อควรระวัง : อย่าลืม update ค่าของประตูให้ครบทั้งสองข้างครั้งเมื่อเดินทางไปถึงสถานีใดๆ

• เมื่อฝั่งซ้ายเป็น คน และฝั่งขวาเป็น ซอมบี้

$dp[i][j][0]=\max(dp[i-1][j][0],dp[i-1][j+R[i]][0]+L[i])$

$dp[i][j][1]=dp[i-1][j][1]$

• เมื่อฝั่งซ้ายเป็น ซอมบี้ และฝั่งขวาเป็น คน

$dp[i][j][1]=\max(dp[i-1][j][1],dp[i-1][j+L[i]][1]+R[i])$

$dp[i][j][0]=dp[i-1][j][0]$

• เมื่อทั้งสองฝั่งเป็นคน

$dp[i][j][0]=dp[i-1][j][0]+L[i]$

$dp[i][j][1]=dp[i-1][j][1]+R[i]$

• เมื่อทั้งสองฝั่งเป็นซอมบี้

$dp[i][j][0]=dp[i-1][j][0]$

$dp[i][j][1]=dp[i-1][j][1]$

คำตอบ : $dp[N][M][0]+dp[N][M][1]$

Time Complexity: $\mathcal{O}(NM)$

Official Solution

การแก้ปัญหาของข้อนี้สามารถนำวิธีการคิดของปัญหาย่อยที่ 4 มาใช้ได้เลย แต่เนื่องจากครั้งนี้อาจมีการสลับประตูเกิดขึ้นได้ $(S=0,1)$ ดังนั้นจึงต้องนำหลักการ Meet in the middle มาช่วยในการหาตำแหน่งของการสลับประตูที่ดีที่สุด แต่เนื่องจากเราไม่ทราบว่าการเดินทาง โดยเริ่มจากสถานีใดๆไปยังเมืองปูซานนั้นจะรับคนได้มากที่สุดเท่าไหร่ จึงจำเป็นต้องมีการวิเคราะห์ปัญหาเพิ่ม

ข้อสังเกต #1 : เนื่องจากเราจำเป็นต้องแยกคิดประตูซ้ายและประตูขวาเพื่อให้โปรแกรมทำงานได้ทันเวลา ดังนั้นจึงไม่สามารถนำหลักการคิดของปัญหาย่อยที่ 2 มาใช้ได้

ข้อสังเกต #2 : เราต้องการทราบว่าการเดินทางโดยเริ่มจากสถานีใดๆไปยังเมืองปูซานนั้นจะรับคนได้มากที่สุดเท่าไหร่ เพื่อหาสถานีและเวลาที่เหมาะสมในการสลับประตู

ข้อสังเกต #3 : เราสามารถมองได้ว่าการเดินทางโดยเริ่มจากสถานีใดๆไปยังเมืองปูซานนั้น ไม่ต่างกับการเดินทางย้อนกลับจากเมืองปูซานไปยังสถานีต่างๆ

ดังนั้นการแก้ปัญหานี้จึงจำเป็นต้องทำ Knapsack 0/1 แยกฝั่ง และ แยกทิศด้วย โดยจะนิยามการทำ dp ดังนี้

$dp[i][j][0]\Rightarrow Left-Forward$

$dp[i][j][1]\Rightarrow Right-Forward$

$dp[i][j][2]\Rightarrow Left-Backward$

$dp[i][j][3]\Rightarrow Right-Backward$

จากนั้นเราจะนำค่าทั้งหมดที่ได้จากการ preprocessing มาใช้ในการหา Middle point โดยจะสังเกตได้ว่าเมื่อสลับประตู ค่าความแข็งแรงปัจจุบันของประตูซ้ายจะกลายเป็นค่าความแข็งแรงปัจจุบันของประตูขวาเมื่อเริ่มต้นที่สถานีถัดไป และในทำนองเดียวกันค่าความแข็งแรงปัจจุบันของประตูขวาจะกลายเป็นค่าความแข็งแรงปัจจุบันของประตูซ้ายเมื่อเริ่มต้นที่สถานีถัดไปเช่นกัน ฉะนั้นเมื่อแยกคิดตามประตู (ไม่ใช่ฝั่ง) เราจะได้จำนวนคนที่มากที่สุดที่สามารถรับได้โดยเกิดจากประตูแต่ละข้างเป็นดังนี้

• เมื่อต้องการสลับประตูที่สถานี $i$ โดยประตูซ้ายโดนโจมตีไปแล้ว $j$ หน่วย

$LeftDoor=dp[i][j][1]+dp[i+1][M-j][2]$

• เมื่อต้องการสลับประตูที่สถานี $i$ โดยประตูขวาโดนโจมตีไปแล้ว $j$ หน่วย

$RightDoor=dp[i][j][0]+dp[i+1][M-j][3]$

Time Complexity: $\mathcal{O}(NM)$

Solution Code

#include "bits/stdc++.h"
using namespace std;
#define DEBUG 0
#define CASES 0

/* --- Official Solution --- */

const int SZ = 2e3+7;
const int MV = 3e3+7;

int L[SZ], R[SZ];
int dp[SZ][MV][4];

/*
0 --> Left Forward
1 --> Right Forward
2 --> Left Backward
3 --> Right Backward

+ --> People
- --> Zombies
*/

void knapsack(int N, int M, bool sym) {
    int l = sym ? 2:0;
    int r = sym ? 3:1;
    int c = sym ? 1:-1;
    int start = sym ? N:1;
    int end = sym ? 0:N+1;

    // Knapsack 0/1
    for(int i=start; i!=end; i-=c) {
        if(L[i]>=0 && R[i]<0) { // (+,-)
            for(int j=0; j<=M; j++) {
                dp[i][j][l] = max(dp[i+c][j][l], j+R[i]>=0 ? dp[i+c][j+R[i]][l] + L[i] : 0);
                dp[i][j][r] = dp[i+c][j][r];
            }
        }
        else if(R[i]>=0 && L[i]<0) { // (-,+)
            for(int j=0; j<=M; j++) {
                dp[i][j][r] = max(dp[i+c][j][r], j+L[i]>=0 ? dp[i+c][j+L[i]][r] + R[i] : 0);
                dp[i][j][l] = dp[i+c][j][l];
            }
        }
        else if(L[i]>=0 && R[i]>=0) { // (+,+)
            for(int j=0; j<=M; j++) {
                dp[i][j][l] = dp[i+c][j][l] + L[i];
                dp[i][j][r] = dp[i+c][j][r] + R[i];
            }
        }
        else { // (-,-)
            for(int j=0; j<=M; j++) {
                dp[i][j][l] = dp[i+c][j][l];
                dp[i][j][r] = dp[i+c][j][r];
            }
        }
    }
}

void process(void) {
    int N, M, S;
    cin >> N >> M >> S;
    for(int i=1; i<=N; i++) cin >> L[i];
    for(int i=1; i<=N; i++) cin >> R[i];

    knapsack(N, M, false); // Forward
    knapsack(N, M, true); // Backward

    int result = dp[N][M][0] + dp[N][M][1]; // default - not swap yet
    
    if(!S) {
        cout << result;
        return ;
    }

    // swap check
    for(int i=1; i<N; i++) {
        int best_left = 0;
        int best_right = 0;
        for(int j=0; j<=M ;j++) {
            best_left = max(best_left, dp[i][j][0] + dp[i+1][M-j][3]);
            best_right = max(best_right, dp[i][j][1] + dp[i+1][M-j][2]);
        }
        result = max(result, best_left + best_right);
    }

    cout << result;

    return ;
}

int main() {
    #ifndef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    cin.tie(nullptr)->ios::sync_with_stdio(false);
    int t(1);
    if(CASES) cin >> t;
    while(t--) process();
}