90402024-02-12 21:21:34BenedekMartonDinamitcpp17Wrong answer 21/5014ms12332 KiB
#include <iostream>
#include <map>
#include <fstream>

using namespace std;

struct s
{
    int mag;
    long long hossz;
    bool elo;
    map <long long, int> robb;
};

int main()
{
    //ifstream cin("be2.txt");
    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;
        //cout << sv << " " << mat[0][0].hossz << endl;
        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;
    }
   // cout << " ok " << endl;
    /*for(map <long long, 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;
       }
            /*cout << i << " " << 0 << endl;
            for(map <long long, int>::iterator it=mat[i][0].robb.begin(); it!=mat[i][0].robb.end(); ++it)
    {
         cout << it->first  << " " << it->second << "  ";
    }
    cout << endl;*/

    }

    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;
        }
            /*cout << 0 << " " << j << endl;
            for(map <long long, int>::iterator it=mat[0][j].robb.begin(); it!=mat[0][j].robb.end(); ++it)
    {
         cout << it->first  << " " << it->second << "  ";
    }
    cout << endl;*/

    }
    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 << i << " " << j << endl;
            for(map <long long, int>::iterator it=mat[i][j].robb.begin(); it!=mat[i][j].robb.end(); ++it)
    {
         cout << it->first  << " " << it->second << "  ";
    }
    cout << endl;*/
        }

    }
    cout << mat[n-1][m-1].hossz;
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base21/50
1Accepted0/03ms1688 KiB
2Wrong answer0/014ms10256 KiB
3Wrong answer0/23ms2656 KiB
4Wrong answer0/23ms2792 KiB
5Wrong answer0/33ms2960 KiB
6Wrong answer0/33ms3172 KiB
7Accepted2/24ms3892 KiB
8Accepted3/34ms4072 KiB
9Wrong answer0/23ms3404 KiB
10Accepted2/23ms3656 KiB
11Accepted3/33ms3732 KiB
12Accepted3/33ms3732 KiB
13Wrong answer0/26ms5384 KiB
14Wrong answer0/34ms5352 KiB
15Wrong answer0/213ms11640 KiB
16Wrong answer0/312ms11664 KiB
17Accepted2/213ms11896 KiB
18Accepted3/313ms12004 KiB
19Wrong answer0/213ms12040 KiB
20Wrong answer0/313ms12096 KiB
21Wrong answer0/212ms12100 KiB
22Accepted3/312ms12332 KiB