252002026-02-18 12:37:55PKBZebra (75 pont)cpp17Accepted 75/751ms564 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> dir(n);
    for (int i = 0; i < n; i++)
        cin >> dir[i];

    vector<long long> A(1, 0), B(1, 0); // 1index

    for (int i = 0; i < n; i++) {
        long long t;
        cin >> t;
        if (dir[i] == 1)
            A.push_back(t);
        else
            B.push_back(t);
    }

    sort(A.begin() + 1, A.end());
    sort(B.begin() + 1, B.end());

    int x = A.size() - 1;
    int y = B.size() - 1;

    const long long INF = 1e18;
    vector<vector<long long>> dp(x + 1, vector<long long>(y + 1, INF));

    dp[0][0] = 0;

    for (int i = 1; i <= x; i++) {
        for (int j = 1; j <= y; j++) {

            long long meet_time = max(A[i], B[j]);
            long long wait = meet_time - B[j];
            for (int k = i; k >= 1; k--) {
                wait += meet_time - A[k];
                dp[i][j] = min(dp[i][j], dp[k - 1][j - 1] + wait);
            }

            wait = meet_time - A[i];
            for (int k = j; k >= 1; k--) {
                wait += meet_time - B[k];
                dp[i][j] = min(dp[i][j], dp[i - 1][k - 1] + wait);
            }
        }
    }

    cout << dp[x][y] << endl;

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base75/75
1Accepted0/01ms512 KiB
2Accepted0/01ms316 KiB
3Accepted5/51ms316 KiB
4Accepted5/51ms508 KiB
5Accepted5/51ms316 KiB
6Accepted5/51ms404 KiB
7Accepted5/51ms564 KiB
8Accepted5/51ms316 KiB
9Accepted5/51ms316 KiB
10Accepted5/51ms316 KiB
11Accepted5/51ms316 KiB
12Accepted5/51ms500 KiB
13Accepted5/51ms316 KiB
14Accepted5/51ms332 KiB
15Accepted5/51ms316 KiB
16Accepted5/51ms316 KiB
17Accepted5/51ms316 KiB