133762025-01-07 17:43:20horkaZebra (75 pont)cpp17Elfogadva 75/753ms556 KiB
#include <bits/stdc++.h>
using namespace std;
const int inf=1e9,c=83;
//int dp[2*c][c][c];
int dp[c][c],ossz1[c][c],ossz2[c][c];
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n; cin>>n;
    vector<int> a{0},b{0};
    for(int i=0; i<c; i++)
        for(int j=0; j<c; j++)
            dp[i][j]=inf;
    vector<int> tip(n+1);
    for(int i=1; i<=n; i++)
        cin>>tip[i];
    for(int i=1; i<=n; i++)
    {
        int x; cin>>x;
        if(tip[i]) b.push_back(x);
        else a.push_back(x);
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    int mera=a.size(),merb=b.size();
    for(int l=1; l<mera; l++)
        for(int r=l; r<mera; r++)
            for(int j=l; j<r; j++)
                ossz1[l][r]+=a[r]-a[j];
    for(int l=1; l<merb; l++)
        for(int r=l; r<merb; r++)
            for(int j=l; j<r; j++)
                ossz2[l][r]+=b[r]-b[j];
    dp[0][0]=0;
    for(int i=1; i<mera; i++)
        for(int j=1; j<merb; j++)
            for(int x=0; x<i; x++)
                for(int y=0; y<j; y++)
    {
        int tmp=dp[x][y];
        int hanya=i-x,hanyb=j-y;
        int veg=max(a[i],b[j]);
        tmp+=ossz1[x+1][i];
        tmp+=ossz2[y+1][j];
        tmp+=hanya*(veg-a[i]);
        tmp+=hanyb*(veg-b[j]);
        dp[i][j]=min(dp[i][j],tmp);
    }
    cout<<dp[mera-1][merb-1]<<"\n";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base75/75
1Elfogadva0/01ms508 KiB
2Elfogadva0/02ms496 KiB
3Elfogadva5/51ms316 KiB
4Elfogadva5/51ms316 KiB
5Elfogadva5/51ms480 KiB
6Elfogadva5/52ms316 KiB
7Elfogadva5/52ms472 KiB
8Elfogadva5/52ms476 KiB
9Elfogadva5/52ms352 KiB
10Elfogadva5/52ms452 KiB
11Elfogadva5/52ms316 KiB
12Elfogadva5/53ms316 KiB
13Elfogadva5/53ms376 KiB
14Elfogadva5/52ms556 KiB
15Elfogadva5/52ms316 KiB
16Elfogadva5/53ms316 KiB
17Elfogadva5/53ms316 KiB