90372024-02-12 20:12:35BenedekMartonDinamitcpp17Wrong answer 16/5012ms10404 KiB
#include <iostream>
#include <map>

using namespace std;

struct s
{
    int mag, hossz;
    bool elo;
    map <int, 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[sv]==0)
        {
            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[sv-sv/2]==0)
            {
                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[sv-sv/2]==0)
            {
                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)
            {
                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[sv-sv/2]==0)
                    {
                        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[sv-sv/2]==0)
                    {
                        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;
}
SubtaskSumTestVerdictTimeMemory
base16/50
1Accepted0/03ms1816 KiB
2Wrong answer0/012ms8300 KiB
3Wrong answer0/23ms2656 KiB
4Wrong answer0/23ms2988 KiB
5Wrong answer0/34ms3104 KiB
6Wrong answer0/33ms3072 KiB
7Accepted2/24ms3648 KiB
8Accepted3/34ms3964 KiB
9Wrong answer0/23ms3604 KiB
10Accepted2/23ms3568 KiB
11Wrong answer0/33ms3828 KiB
12Accepted3/33ms4040 KiB
13Wrong answer0/24ms5216 KiB
14Wrong answer0/34ms5328 KiB
15Wrong answer0/212ms10216 KiB
16Wrong answer0/312ms10316 KiB
17Wrong answer0/212ms10404 KiB
18Accepted3/312ms10312 KiB
19Wrong answer0/212ms10324 KiB
20Wrong answer0/312ms10340 KiB
21Wrong answer0/212ms10312 KiB
22Accepted3/312ms10392 KiB