9039 | 2024. 02. 12 20:36:08 | BenedekMarton | Dinamit | cpp17 | Hibás válasz 21/50 | 13ms | 11616 KiB |
#include <iostream>
#include <map>
using namespace std;
struct s
{
int mag;
long long hossz;
bool elo;
map <long long, int> robb;
};
int main()
{
int n, m, k;
cin >> n >> m >> k;
s mat[n][m];
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
cin >> mat[i][j].mag;
}
}
mat[0][0].hossz=mat[0][0].mag;
int sv;
for(int i=0; i<k; i++)
{
sv=mat[0][0].hossz-mat[0][0].hossz/2;
if(mat[0][0].robb.find(sv)==mat[0][0].robb.end())
{
mat[0][0].robb[sv]=1;
}
else
{
mat[0][0].robb[sv]++;
}
mat[0][0].hossz=mat[0][0].hossz/2;
}
/*for(map <int, int>::iterator it=mat[0][0].robb.begin(); it!=mat[0][0].robb.end(); ++it)
{
cout << it->first << " " << it->second << endl;
}*/
for(int i=1; i<n; i++)
{
mat[i][0].elo=1;
mat[i][0].hossz=mat[i][0].mag+mat[i-1][0].hossz;
for(auto & [kulcs, ertek]: mat[i-1][0].robb)
{
mat[i][0].robb[kulcs]=ertek;
}
sv=mat[i][0].mag;
while(sv-sv/2>mat[i][0].robb.begin()->first)
{
mat[i][0].hossz=mat[i][0].hossz-(sv-sv/2);
mat[i][0].hossz=mat[i][0].hossz+mat[i][0].robb.begin()->first;
if(mat[i][0].robb.begin()->second==1)
{
mat[i][0].robb.erase(mat[i][0].robb.begin());
}
else
{
mat[i][0].robb.begin()->second--;
}
if(mat[i][0].robb.find(sv-sv/2)==mat[i][0].robb.end())
{
mat[i][0].robb[sv-sv/2]=1;
}
else
{
mat[i][0].robb[sv-sv/2]++;
}
sv=sv/2;
}
}
for(int j=1; j<m; j++)
{
mat[0][j].elo=0;
mat[0][j].hossz=mat[0][j].mag+mat[0][j-1].hossz;
for(auto & [kulcs, ertek]: mat[0][j-1].robb)
{
mat[0][j].robb[kulcs]=ertek;
}
sv=mat[0][j].mag;
while(sv-sv/2>mat[0][j].robb.begin()->first)
{
mat[0][j].hossz=mat[0][j].hossz-(sv-sv/2);
mat[0][j].hossz=mat[0][j].hossz+mat[0][j].robb.begin()->first;
if(mat[0][j].robb.begin()->second==1)
{
mat[0][j].robb.erase(mat[0][j].robb.begin());
}
else
{
mat[0][j].robb.begin()->second--;
}
if(mat[0][j].robb.find(sv-sv/2)==mat[0][j].robb.end())
{
mat[0][j].robb[sv-sv/2]=1;
}
else
{
mat[0][j].robb[sv-sv/2]++;
}
sv=sv/2;
}
}
for(int i=1; i<n; i++)
{
for(int j=1; j<m; j++)
{
if(mat[i-1][j].hossz<mat[i][j-1].hossz or (mat[i-1][j].hossz==mat[i][j-1].hossz and mat[i-1][j].robb.begin()->first<mat[i][j-1].robb.begin()->first))
{
mat[i][j].elo=1;
mat[i][j].hossz=mat[i][j].mag+mat[i-1][j].hossz;
for(auto & [kulcs, ertek]: mat[i-1][j].robb)
{
mat[i][j].robb[kulcs]=ertek;
}
sv=mat[i][j].mag;
while(sv-sv/2>mat[i][j].robb.begin()->first)
{
mat[i][j].hossz=mat[i][j].hossz-(sv-sv/2);
mat[i][j].hossz=mat[i][j].hossz+mat[i][j].robb.begin()->first;
if(mat[i][j].robb.begin()->second==1)
{
mat[i][j].robb.erase(mat[i][j].robb.begin());
}
else
{
mat[i][j].robb.begin()->second--;
}
if(mat[i][j].robb.find(sv-sv/2)==mat[i][j].robb.end())
{
mat[i][j].robb[sv-sv/2]=1;
}
else
{
mat[i][j].robb[sv-sv/2]++;
}
sv=sv/2;
}
}
else
{
mat[i][j].elo=0;
mat[i][j].hossz=mat[i][j].mag+mat[i][j-1].hossz;
for(auto & [kulcs, ertek]: mat[i][j-1].robb)
{
mat[i][j].robb[kulcs]=ertek;
}
sv=mat[i][j].mag;
while(sv-sv/2>mat[i][j].robb.begin()->first)
{
mat[i][j].hossz=mat[i][j].hossz-(sv-sv/2);
mat[i][j].hossz=mat[i][j].hossz+mat[i][j].robb.begin()->first;
if(mat[i][j].robb.begin()->second==1)
{
mat[i][j].robb.erase(mat[i][j].robb.begin());
}
else
{
mat[i][j].robb.begin()->second--;
}
if(mat[i][j].robb.find(sv-sv/2)==mat[i][j].robb.end())
{
mat[i][j].robb[sv-sv/2]=1;
}
else
{
mat[i][j].robb[sv-sv/2]++;
}
sv=sv/2;
}
}
}
}
cout << mat[n-1][m-1].hossz;
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 21/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1816 KiB | |||
2 | Hibás válasz | 0/0 | 13ms | 10208 KiB | |||
3 | Hibás válasz | 0/2 | 3ms | 2688 KiB | |||
4 | Hibás válasz | 0/2 | 3ms | 2764 KiB | |||
5 | Hibás válasz | 0/3 | 3ms | 2996 KiB | |||
6 | Hibás válasz | 0/3 | 3ms | 3280 KiB | |||
7 | Elfogadva | 2/2 | 4ms | 4208 KiB | |||
8 | Elfogadva | 3/3 | 4ms | 4336 KiB | |||
9 | Hibás válasz | 0/2 | 3ms | 3548 KiB | |||
10 | Elfogadva | 2/2 | 3ms | 3552 KiB | |||
11 | Elfogadva | 3/3 | 3ms | 3696 KiB | |||
12 | Elfogadva | 3/3 | 3ms | 3436 KiB | |||
13 | Hibás válasz | 0/2 | 4ms | 5252 KiB | |||
14 | Hibás válasz | 0/3 | 4ms | 5236 KiB | |||
15 | Hibás válasz | 0/2 | 12ms | 11388 KiB | |||
16 | Hibás válasz | 0/3 | 12ms | 11268 KiB | |||
17 | Elfogadva | 2/2 | 12ms | 11264 KiB | |||
18 | Elfogadva | 3/3 | 12ms | 11416 KiB | |||
19 | Hibás válasz | 0/2 | 12ms | 11388 KiB | |||
20 | Hibás válasz | 0/3 | 12ms | 11396 KiB | |||
21 | Hibás válasz | 0/2 | 12ms | 11468 KiB | |||
22 | Elfogadva | 3/3 | 12ms | 11616 KiB |