105472024-04-05 01:42:33oZebra (75 pont)cpp17Elfogadva 75/753ms3772 KiB
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> c(N);
    for (int i = 0; i < N; i++)
    {
        cin >> c[i];
    }
    vector<int> a, b;
    for (int i = 0; i < N; i++)
    {
        int x;
        cin >> x;
        (c[i] ? a : b).push_back(x);
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    int n = a.size(), m = b.size();
    vector<int> pa(n + 1), pb(m + 1);
    for (int i = 0; i < n; i++)
    {
        pa[i + 1] = pa[i] + a[i];
    }
    for (int i = 0; i < m; i++)
    {
        pb[i + 1] = pb[i] + b[i];
    }
    int dp[n + 1][m + 1];
    for (int i = 0; i <= n; i++)
    {
        dp[i][0] = 1e9;
    }
    for (int i = 0; i <= m; i++)
    {
        dp[0][i] = 1e9;
    }
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            int l = max(a[i - 1], b[j - 1]);
            dp[i][j] = l * (i + j) - pa[i] - pb[j];
            for (int ii = 0; ii < i; ii++)
            {
                int jj = j - 1;
                dp[i][j] = min(dp[i][j], dp[ii][jj] + l * (i + j - ii - jj) - pa[i] - pb[j] + pa[ii] + pb[jj]);
            }
            for (int jj = 0; jj < j; jj++)
            {
                int ii = i - 1;
                dp[i][j] = min(dp[i][j], dp[ii][jj] + l * (i + j - ii - jj) - pa[i] - pb[j] + pa[ii] + pb[jj]);
            }
        }
    }
    cout << dp[n][m] << '\n';
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base75/75
1Elfogadva0/03ms1816 KiB
2Elfogadva0/03ms2020 KiB
3Elfogadva5/53ms2228 KiB
4Elfogadva5/53ms2448 KiB
5Elfogadva5/53ms2684 KiB
6Elfogadva5/53ms2772 KiB
7Elfogadva5/53ms2740 KiB
8Elfogadva5/53ms2740 KiB
9Elfogadva5/53ms2876 KiB
10Elfogadva5/53ms3112 KiB
11Elfogadva5/53ms3320 KiB
12Elfogadva5/53ms3448 KiB
13Elfogadva5/53ms3536 KiB
14Elfogadva5/53ms3536 KiB
15Elfogadva5/53ms3536 KiB
16Elfogadva5/53ms3528 KiB
17Elfogadva5/53ms3772 KiB