Beküldés #4 501

2023-03-29 10:59:57

cpp14

Elfogadva 50/50

26ms

5324 KiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int 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 (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            cin >> t[i][j];
        }
    }
    dp[1][1][0] = t[1][1];
    for (int i=1; i<=k; i++){
        dp[1][1][i] = dp[1][1][i-1] / 2;
    }
    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            for (int l=0; l<=k; l++){
                for (int 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];
}

	Összpont	Teszt	Verdikt		Idő	Memória
base	50/50
		1	Elfogadva	0/0	3ms	1688 KiB
		2	Elfogadva	0/0	26ms	3072 KiB
		3	Elfogadva	2/2	3ms	2300 KiB
		4	Elfogadva	2/2	3ms	2556 KiB
		5	Elfogadva	3/3	3ms	2772 KiB
		6	Elfogadva	3/3	3ms	2984 KiB
		7	Elfogadva	2/2	25ms	4236 KiB
		8	Elfogadva	3/3	26ms	4540 KiB
		9	Elfogadva	2/2	4ms	3652 KiB
		10	Elfogadva	2/2	4ms	3636 KiB
		11	Elfogadva	3/3	4ms	3644 KiB
		12	Elfogadva	3/3	4ms	3660 KiB
		13	Elfogadva	2/2	8ms	4104 KiB
		14	Elfogadva	3/3	8ms	4308 KiB
		15	Elfogadva	2/2	26ms	5200 KiB
		16	Elfogadva	3/3	26ms	5136 KiB
		17	Elfogadva	2/2	26ms	5144 KiB
		18	Elfogadva	3/3	26ms	5144 KiB
		19	Elfogadva	2/2	26ms	5148 KiB
		20	Elfogadva	3/3	26ms	5304 KiB
		21	Elfogadva	2/2	26ms	5324 KiB
		22	Elfogadva	3/3	26ms	5320 KiB