41322023-03-15 11:38:53horvathabelDinamitcpp17Hibás válasz 23/503ms4128 KiB
#include <bits/stdc++.h>
#include <queue>
using namespace std;

int main() {
	int n,m,k;
	cin>>n>>m>>k;
	pair<int,int> dp[n+1][m+1];
	int mgs[n+1][m+1];
	for (int i=0; i<n;i++){
		for (int j=0; j<m;j++){
			int x;
			cin>>x;
			mgs[i][j]=x; 
			if (i==0 && j==0) dp[0][0]={x,-1};
			if (i==0 && j!=0) dp[0][j]={dp[0][j-1].first+x,0};
			if (i!=0 && j==0) dp[i][0]={dp[i-1][0].first+x,1};
		}
	}
for (int i=1; i<n;i++){
	for (int j=1; j<m;j++){
		if (dp[i-1][j].first<dp[i][j-1].first){
			dp[i][j]={dp[i-1][j].first+mgs[i][j],1};
		}
		else{
			dp[i][j]={dp[i][j-1].first+mgs[i][j],0};
		}
		
	}
}
priority_queue<int> q; 
pair<int, int> a={n-1,m-1};

	vector<int> z;
while (a.first!=0 or a.second!=0){
	q.push(mgs[a.first][a.second]);
	z.push_back(mgs[a.first][a.second]);
	if (dp[a.first][a.second].second==0) a.second--;
	else a.first--;
}	
q.push(mgs[0][0]);

int ans=dp[n-1][m-1].first;
for (int i=0; i<k;i++){
	int z=q.top(),u=q.top();
	
	q.pop();
	z/=2;
	ans-=u-z;
	q.push(z);
}
cout<<ans; 

}


RészfeladatÖsszpontTesztVerdiktIdőMemória
base23/50
1Elfogadva0/03ms1980 KiB
2Hibás válasz0/03ms2160 KiB
3Elfogadva2/23ms2196 KiB
4Elfogadva2/23ms2260 KiB
5Elfogadva3/33ms2396 KiB
6Elfogadva3/33ms2476 KiB
7Elfogadva2/23ms2712 KiB
8Elfogadva3/33ms2936 KiB
9Hibás válasz0/23ms3028 KiB
10Elfogadva2/23ms3248 KiB
11Elfogadva3/33ms3456 KiB
12Hibás válasz0/33ms3668 KiB
13Hibás válasz0/23ms3732 KiB
14Elfogadva3/33ms3708 KiB
15Hibás válasz0/23ms3716 KiB
16Hibás válasz0/33ms3720 KiB
17Hibás válasz0/23ms3716 KiB
18Hibás válasz0/33ms3720 KiB
19Hibás válasz0/23ms3704 KiB
20Hibás válasz0/33ms3828 KiB
21Hibás válasz0/23ms4040 KiB
22Hibás válasz0/33ms4128 KiB