143952025-01-10 18:03:47UVinceFestés (50 pont)cpp17Hibás válasz 26/50293ms38712 KiB
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,m;
    cin>>n>>m;

    vector<ll> rcost(n);
    for (auto &i : rcost) cin>>i;
    vector<vector<vector<ll>>> ccost(m, vector<vector<ll>> (n+1, vector<ll> (n+1, -1)));
    for (auto &c : ccost){
        for (int i=1;i<=n;i++){
            for (int j=i;j<=n;j++){
                cin>>c[i][j];
            }
        }
    }
    

    ll ans=LLONG_MAX;

    for (int bitmask=0;bitmask<(1<<n);bitmask++){
        ll cost=0;
        for (int i=0;i<n;i++) if ((bitmask>>i) & 1) cost+=rcost[i];
        for (int i=0;i<m;i++){
            vector<ll> dp(n+1, LLONG_MAX);
            dp[0]=0;
            for (int j=1;j<=n;j++) {
                if ((bitmask>>(j-1)) & 1) dp[j]=dp[j-1];
                for (int k=1;k<=j;k++){
                    dp[j]=min(dp[j], dp[k-1]+ccost[i][k][j]);
                }
            }
            cost+=dp[n];
        }
        ans=min(ans,cost);
    }
    cout<<ans;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base26/50
1Elfogadva0/01ms316 KiB
2Hibás válasz0/01ms316 KiB
3Elfogadva2/2156ms32308 KiB
4Hibás válasz0/21ms316 KiB
5Elfogadva3/33ms564 KiB
6Hibás válasz0/225ms4152 KiB
7Elfogadva2/2282ms38632 KiB
8Hibás válasz0/2256ms38708 KiB
9Hibás válasz0/2282ms38624 KiB
10Elfogadva2/2256ms38712 KiB
11Hibás válasz0/2256ms38452 KiB
12Hibás válasz0/2263ms35380 KiB
13Hibás válasz0/2268ms35412 KiB
14Elfogadva2/282ms19764 KiB
15Elfogadva3/383ms19756 KiB
16Elfogadva3/3165ms32412 KiB
17Elfogadva2/2150ms32308 KiB
18Elfogadva3/3165ms32400 KiB
19Elfogadva2/2229ms34932 KiB
20Hibás válasz0/2268ms36672 KiB
21Hibás válasz0/2280ms38320 KiB
22Hibás válasz0/2257ms38632 KiB
23Hibás válasz0/2259ms38708 KiB
24Hibás válasz0/2282ms38708 KiB
25Elfogadva2/2293ms38708 KiB