44982023-03-29 10:50:15ZsofiaKeresztelyDinamitcpp14Hibás válasz 18/5025ms5004 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    ll n, m, k;
    cin >> n >> m >> k;
    vector<vector<ll> > t(n+1, vector<ll>(m+1, 0));
    vector<vector<vector<ll> > > dp(n+1, vector<vector<ll> >(m+1, vector<ll>(k+1, INT_MAX/2)));
    for (ll i=1; i<=n; i++){
        for (ll j=1; j<=m; j++){
            cin >> t[i][j];
        }
    }
    dp[1][1][0] = t[1][1];
    for (ll i=1; i<=n; i++){
        for (ll j=1; j<=m; j++){
            dp[i][j][0] = min(dp[i][j][0], t[i][j]+min(dp[i][j-1][0], dp[i-1][j][0]));
            for (ll l=1; l<=k; l++){
                dp[i][j][l] = dp[i][j][l-1];
                for (ll x=0; x<=l; x++){
                    dp[i][j][l] = min(dp[i][j][l], t[i][j]/(1 << x)+min(dp[i][j-1][l-x], dp[i-1][j][l-x]));
                }
            }
        }
    }
    cout << dp[n][m][k];
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base18/50
1Elfogadva0/03ms1816 KiB
2Hibás válasz0/025ms3280 KiB
3Elfogadva2/23ms2500 KiB
4Elfogadva2/23ms2720 KiB
5Elfogadva3/33ms2804 KiB
6Elfogadva3/33ms2944 KiB
7Elfogadva2/224ms4340 KiB
8Hibás válasz0/325ms4148 KiB
9Hibás válasz0/24ms3104 KiB
10Hibás válasz0/24ms3168 KiB
11Hibás válasz0/34ms3492 KiB
12Hibás válasz0/34ms3636 KiB
13Elfogadva2/28ms3788 KiB
14Hibás válasz0/38ms3752 KiB
15Elfogadva2/225ms4888 KiB
16Hibás válasz0/325ms4744 KiB
17Hibás válasz0/225ms4740 KiB
18Hibás válasz0/325ms4688 KiB
19Elfogadva2/225ms4692 KiB
20Hibás válasz0/325ms4692 KiB
21Hibás válasz0/225ms4824 KiB
22Hibás válasz0/325ms5004 KiB