PROG-1159: จัดลำดับการทดลอง (schedule)

#include <bits/stdc++.h>

using namespace std;
const int INF = 1e9;
const int N = 1e3 + 10;
const int M = 6e2 + 10;
int day[N][N], tim[N][N];
int qsA[N], qsB[N], minA[N], minB[N];
int n, m;

int SumA(int i, int j){
    return qsA[j] - qsA[i-1];
}

int SumB(int i, int j){
    return qsB[j] - qsB[i-1];
}

void Solve(int a, int b, int cur_day, int cur_time){
    if(cur_day < day[a][b]){
        day[a][b] = cur_day;
        tim[a][b] = cur_time;
    }
    else if(cur_day == day[a][b]){
        tim[a][b] = min(tim[a][b], cur_time);
    }
}

int MinA(int idx){
    int r = idx, l = 1, mn = idx;
    while(l <= r){
        int mid = (l + r) / 2;
        if(SumA(mid, idx) <= m){
            mn = min(mn, mid);
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    return mn;
}

int MinB(int idx){
    int r = idx, l = 1, mn = idx;
    while(l <= r){
        int mid = (l + r) / 2;
        if(SumB(mid, idx) <= m){
            mn = min(mn, mid);
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    return mn;
}

int main(){

    scanf("%d%d", &m, &n);

    for(int i=1;i<=n;i++){
        scanf("%d", &qsA[i]);
        qsA[i] += qsA[i-1];
        minA[i] = MinA(i);
    }
    for(int i=1;i<=n;i++){
        scanf("%d", &qsB[i]);
        qsB[i] += qsB[i-1];
        minB[i] = MinB(i);
    }

    for(int a=0;a<=n;a++){
        for(int b=0;b<=n;b++){
            if(a == 0 and b == 0) continue;
            day[a][b] = tim[a][b] = INF;
            if(a > 0){
                /// A
                for(int ia=minA[a];ia<=a;ia++){
                    int cur_day = 1 + day[ia - 1][b];
                    int cur_time = SumA(ia, a);
                    Solve(a, b, cur_day, cur_time);
                }
            }
            if(b > 0){
                /// B
                for(int ib=minB[b];ib<=b;ib++){
                    int cur_day = 1 + day[a][ib - 1];
                    int cur_time = SumB(ib, b);
                    Solve(a, b, cur_day, cur_time);
                }
            }
            if(a > 0 and b > 0){
                /// A & B
                int ib = b + 1;
                for(int ia=minA[a];ia<=a;ia++){
                    while(SumA(ia, a) + SumB(ib - 1, b) <= m and 1 < ib){
                        ib --;
                    }
                    int cur_day = 1 + day[ia - 1][ib - 1];
                    int cur_time = SumA(ia, a) + SumB(ib, b);
                    Solve(a, b, cur_day, cur_time);
                }
            }
        }
    }

    printf("%d\n%d", day[n][n], tim[n][n]);

    return 0;
}