15 months ago

Mousam Kumari • 0

Guwahati

Code of above ⬆
it will give tle please optimize it.

#include<bits/stdc++.h>
using namespace std;
#define int long long

int solve(int n, vector<int>& front, vector<int>& back, int frontend, int backend) {
    vector<vector<int>> dp(n + 1, vector<int>(frontend + 1, INT_MAX));
    dp[0][0] = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= frontend; j++) {
            if (dp[i][j] == INT_MAX) continue;
            if (j < frontend) {
                dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + front[i]);
            }
            int b = i - j;
            if (b < backend) {
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + back[i]);
            }
        }
    }

    return dp[n][frontend];
}

int32_t main() {
    int frontend, backend;
    cin >> frontend >> backend;
    int n = frontend + backend;
    vector<int> front(n), back(n);
    
    for (int i = 0; i < n; i++) {
        cin >> front[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> back[i];
    }

    int result = solve(n, front, back, frontend, backend);
    cout << result << endl;

    return 0;
}

//input ke according function name change kar lena