9037 2024. 02. 12 20:12:35 BenedekMarton Dinamit cpp17 Hibás válasz 16/50 12ms 10404 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 16/50
1 Elfogadva 0/0 3ms 1816 KiB
2 Hibás válasz 0/0 12ms 8300 KiB
3 Hibás válasz 0/2 3ms 2656 KiB
4 Hibás válasz 0/2 3ms 2988 KiB
5 Hibás válasz 0/3 4ms 3104 KiB
6 Hibás válasz 0/3 3ms 3072 KiB
7 Elfogadva 2/2 4ms 3648 KiB
8 Elfogadva 3/3 4ms 3964 KiB
9 Hibás válasz 0/2 3ms 3604 KiB
10 Elfogadva 2/2 3ms 3568 KiB
11 Hibás válasz 0/3 3ms 3828 KiB
12 Elfogadva 3/3 3ms 4040 KiB
13 Hibás válasz 0/2 4ms 5216 KiB
14 Hibás válasz 0/3 4ms 5328 KiB
15 Hibás válasz 0/2 12ms 10216 KiB
16 Hibás válasz 0/3 12ms 10316 KiB
17 Hibás válasz 0/2 12ms 10404 KiB
18 Elfogadva 3/3 12ms 10312 KiB
19 Hibás válasz 0/2 12ms 10324 KiB
20 Hibás válasz 0/3 12ms 10340 KiB
21 Hibás válasz 0/2 12ms 10312 KiB
22 Elfogadva 3/3 12ms 10392 KiB