84592024-01-16 20:37:35bovizdbFestés (50 pont)cpp17Hibás válasz 11/50257ms69504 KiB
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define endl "\n"
#define pll pair<ll, ll>
#define fs first
#define sc second
#define vll vector<ll>
#define v2d vector<vector<ll>>
#define vpll vector<pll>
#define qll queue<ll>
#define stll stack<ll>
#define sll set<ll>
#define mll map<ll, ll>

ll n, m;
vll r;
vector<v2d> c;
int b = 0b0000;


void solve()
{
    cin >> n >> m;
    r.resize(m);
    c.resize(m, v2d(n, vll(n)));
    for (ll i = 0; i < n; i++) cin >> r[i];
    for (ll i = 0; i < m; i++)
    {
        for (ll j = 0; j < n; j++)
        {
            for (ll k = j; k < n; k++) cin >> c[i][j][k];
        }
    }
    ll out = LONG_MAX;
    for (ll i = 0; i < (1<<n); i++)
    {
        ll cost = 0;
        for (ll j = 0; j < n; j++) cost += bitset<4>(b)[j]*r[j];
        for (ll k = 0; k < m; k++)
        {
            vll dp(n);
            for (ll j = 0; j < n; j++)
            {
                if (j == 0)
                {
                    if (bitset<4>(b)[j] == 0) dp[0] = c[k][0][0];
                    continue;
                }
                if (bitset<4>(b)[j] == 1) dp[j] = min(dp[j-1], c[k][0][j]);
                else
                {
                    ll mn = c[k][0][j];
                    for (ll l = 1; l <= j; l++) mn = min(mn, dp[l-1]+c[k][l][j]);
                    dp[j] = mn;
                }
            }
            cost += dp[n-1];
        }
        out = min(out, cost);
        b += 1;
    }
    cout << out;
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll t = 1;
    //cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base11/50
1Elfogadva0/03ms1860 KiB
2Hibás válasz0/03ms2152 KiB
3Elfogadva2/2143ms42816 KiB
4Hibás válasz0/23ms2608 KiB
5Hibás válasz0/34ms3264 KiB
6Hibás válasz0/225ms9164 KiB
7Elfogadva2/2248ms68492 KiB
8Hibás válasz0/2248ms68724 KiB
9Hibás válasz0/2247ms68852 KiB
10Hibás válasz0/2248ms68864 KiB
11Hibás válasz0/2246ms68476 KiB
12Hibás válasz0/2226ms63148 KiB
13Hibás válasz0/2238ms63404 KiB
14Elfogadva2/278ms34376 KiB
15Elfogadva3/379ms34376 KiB
16Hibás válasz0/3136ms43864 KiB
17Elfogadva2/2136ms43940 KiB
18Hibás válasz0/3136ms44008 KiB
19Hibás válasz0/2224ms62460 KiB
20Hibás válasz0/2237ms65884 KiB
21Hibás válasz0/2247ms68440 KiB
22Hibás válasz0/2248ms69356 KiB
23Hibás válasz0/2248ms69356 KiB
24Hibás válasz0/2250ms69352 KiB
25Hibás válasz0/2257ms69504 KiB