293482026-06-09 14:00:45KristófRendőr **cpp17Elfogadva 100/100112ms31384 KiB
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int INF=1e9;
int main()
{
    int n,m=0;cin>>n;
    vector<int> rendorok;
    vector<int> alap(n+1);
    for(int i=1;i<=n;i++)
        {
        cin>>alap[i];m+=alap[i];
        }
    for(int i=1;i<=n;i++)
        {
        int j=0;
        while(++j<=alap[i])rendorok.push_back(i);
        }
    vector<vector<int>> dp(505,vector<int> (505,INF));
    vector<vector<vector<bool>>> sorozat(505,vector<vector<bool>> (505,vector<bool> (505,0)));
    for(int i=0;i<=n;i++)dp[0][i]=0;
    for(int i=1;i<=m;i++)
        {
        for(int j=i;j<=n;j++)
            {
            int before=dp[i][j-1];
            int jedik=dp[i-1][j-1]+abs(rendorok[i-1]-j);
            if(before<jedik)
                {
                dp[i][j]=before;
                sorozat[i][j]=sorozat[i][j-1];
                }
            else
                {
                dp[i][j]=jedik;
                sorozat[i][j]=sorozat[i-1][j-1];
                sorozat[i][j][j]=1;
                }
            }
        }
    cout<<dp[m][n]<<"\n";
    for(int i=1;i<=n;i++)cout<<sorozat[m][n][i]<<" ";

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base100/100
1Elfogadva6/686ms31284 KiB
2Elfogadva6/686ms31284 KiB
3Elfogadva6/693ms31288 KiB
4Elfogadva6/693ms31284 KiB
5Elfogadva6/694ms31276 KiB
6Elfogadva7/794ms31268 KiB
7Elfogadva7/793ms31284 KiB
8Elfogadva7/789ms31200 KiB
9Elfogadva7/797ms31284 KiB
10Elfogadva7/793ms31284 KiB
11Elfogadva7/7101ms31312 KiB
12Elfogadva7/798ms31384 KiB
13Elfogadva7/7108ms31300 KiB
14Elfogadva7/7104ms31284 KiB
15Elfogadva7/7112ms31284 KiB