9038 2024. 02. 12 20:17:57 BenedekMarton Dinamit cpp17 Hibás válasz 21/50 12ms 9516 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 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[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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 21/50
1 Elfogadva 0/0 3ms 2088 KiB
2 Hibás válasz 0/0 12ms 8404 KiB
3 Hibás válasz 0/2 3ms 2568 KiB
4 Hibás válasz 0/2 3ms 2632 KiB
5 Hibás válasz 0/3 3ms 2812 KiB
6 Hibás válasz 0/3 3ms 2792 KiB
7 Elfogadva 2/2 4ms 3888 KiB
8 Elfogadva 3/3 4ms 3884 KiB
9 Hibás válasz 0/2 3ms 3292 KiB
10 Elfogadva 2/2 3ms 3432 KiB
11 Elfogadva 3/3 3ms 3384 KiB
12 Elfogadva 3/3 3ms 3380 KiB
13 Hibás válasz 0/2 4ms 4784 KiB
14 Hibás válasz 0/3 4ms 4732 KiB
15 Hibás válasz 0/2 10ms 9356 KiB
16 Hibás válasz 0/3 10ms 9364 KiB
17 Elfogadva 2/2 10ms 9456 KiB
18 Elfogadva 3/3 10ms 9360 KiB
19 Hibás válasz 0/2 10ms 9516 KiB
20 Hibás válasz 0/3 12ms 9476 KiB
21 Hibás válasz 0/2 12ms 9444 KiB
22 Elfogadva 3/3 10ms 9436 KiB