94162024-02-21 14:28:09ananászDinamitcpp17Wrong answer 23/503ms4352 KiB
// dinamit.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main()
{
	long long N, M, K;
	cin >> N >> M >> K;
	vector<vector<long long>>sum(N, vector<long long>(M, 0));
	vector<vector<long long>>faradtsag(N, vector<long long>(M, 0));
	//vector<vector<long long>>paratlandb(N, vector<long long>(M, 0));
	for (long long i = 0; i < N; i++)
	{
		for (long long j = 0; j < M; j++)
		{
			cin >> faradtsag[i][j];
		}
	}
	sum[0][0] = faradtsag[0][0];
	/*if (faradtsag[0][0] % 2 == 1)
	{
		paratlandb[0][0]++;
	}*/
	for (long long i = 1; i < M; i++)
	{
		sum[0][i] = sum[0][i - 1] + faradtsag[0][i];
		/*if (faradtsag[0][i] % 2 == 1)
		{
			paratlandb[0][i]++;
		}*/
	}
	for (long long i = 1; i < N; i++)
	{
		for (long long j = 0; j < M; j++)
		{
			if (j == 0)
			{
				sum[i][j] = sum[i - 1][0] + faradtsag[i][j];
			}
			else
			{
				if (sum[i - 1][j]< sum[i][j - 1])
				{
					sum[i][j] = sum[i - 1][j] + faradtsag[i][j];
					//paratlandb[i][j] += paratlandb[i - 1][j];
				}
				else //if (sum[i - 1][j] < sum[i][j - 1])
				{
					sum[i][j] = sum[i][j-1] + faradtsag[i][j];
					//paratlandb[i][j] += paratlandb[i][j-1];
				}
				/*else
				{
					if (paratlandb[i][j - 1]< paratlandb[i-1][j])
					{
						sum[i][j] = sum[i][j-1] + faradtsag[i][j];
						paratlandb[i][j] += paratlandb[i ][j- 1];
					}
					else
					{
						sum[i][j] = sum[i-1][j] + faradtsag[i][j];
						paratlandb[i][j] += paratlandb[i-1][j];
					}
				}*/
			}
			/*if (faradtsag[i][j] % 2 == 1)
			{
				paratlandb[i][j]++;
			}*/
		}
	}
	//long long ertek= sum[N-1][M-1];
	priority_queue<long long>robbantas;
	pair<long long, long long>akt;
	robbantas.push(faradtsag[N - 1][M - 1]);
	akt.first = N - 1;
	akt.second = M - 1;
	while (akt.first > 0 && akt.second > 0)
	{
		if (sum[akt.first - 1][akt.second] < sum[akt.first][akt.second - 1])
		{
			akt.first--;
		}
		else if (sum[akt.first - 1][akt.second] > sum[akt.first][akt.second - 1])
		{
			akt.second--;
		}
		else
		{
			if (faradtsag[akt.first - 1][akt.second]%2==0&&faradtsag[akt.first][akt.second - 1]%2==1)
			{
				akt.first--;
			}
			else
			{
				akt.second--;
			}
		}
		/*else {
			if (paratlandb[akt.first][akt.second - 1] < paratlandb[akt.first - 1][akt.second])
			{
				akt.first--;
			}
			else
			{
				akt.second--;
			}
		}*/
		robbantas.push(faradtsag[akt.first][akt.second]);
	}
	while (akt.first > 0)
	{
		akt.first--;
		robbantas.push(faradtsag[akt.first][akt.second]);
	}
	while (akt.second > 0)
	{
		akt.second--;
		robbantas.push(faradtsag[akt.first][akt.second]);
	}
	long long x;
	long long y;
	for (long long i = 0; i < K; i++)
	{
		/*x=robbantas.top();

		if (x%2==0)
		{
			x = x / 2;
			y = x;
		}
		else
		{
			x = x / 2;
			y=x+1;
		}
		ertek -= y;*/
		robbantas.push(robbantas.top() / 2);
		robbantas.pop();
	}
	long long ertek = 0;
	while (robbantas.size() > 0)
	{
		ertek += robbantas.top();
		robbantas.pop();
	}
	cout << ertek << endl;
	return 0;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file
SubtaskSumTestVerdictTimeMemory
base23/50
1Accepted0/03ms1816 KiB
2Wrong answer0/03ms2080 KiB
3Accepted2/23ms2436 KiB
4Accepted2/23ms2524 KiB
5Accepted3/33ms2692 KiB
6Accepted3/33ms2668 KiB
7Accepted2/23ms2880 KiB
8Accepted3/33ms3004 KiB
9Wrong answer0/23ms3192 KiB
10Accepted2/23ms3304 KiB
11Accepted3/33ms3404 KiB
12Wrong answer0/33ms3524 KiB
13Wrong answer0/23ms3444 KiB
14Accepted3/33ms3448 KiB
15Wrong answer0/23ms3748 KiB
16Wrong answer0/33ms3788 KiB
17Wrong answer0/23ms4264 KiB
18Wrong answer0/33ms4080 KiB
19Wrong answer0/23ms4080 KiB
20Wrong answer0/33ms4352 KiB
21Wrong answer0/23ms4336 KiB
22Wrong answer0/33ms4216 KiB