9040 2024. 02. 12 21:21:34 BenedekMarton Dinamit cpp17 Hibás válasz 21/50 14ms 12332 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 21/50
1 Elfogadva 0/0 3ms 1688 KiB
2 Hibás válasz 0/0 14ms 10256 KiB
3 Hibás válasz 0/2 3ms 2656 KiB
4 Hibás válasz 0/2 3ms 2792 KiB
5 Hibás válasz 0/3 3ms 2960 KiB
6 Hibás válasz 0/3 3ms 3172 KiB
7 Elfogadva 2/2 4ms 3892 KiB
8 Elfogadva 3/3 4ms 4072 KiB
9 Hibás válasz 0/2 3ms 3404 KiB
10 Elfogadva 2/2 3ms 3656 KiB
11 Elfogadva 3/3 3ms 3732 KiB
12 Elfogadva 3/3 3ms 3732 KiB
13 Hibás válasz 0/2 6ms 5384 KiB
14 Hibás válasz 0/3 4ms 5352 KiB
15 Hibás válasz 0/2 13ms 11640 KiB
16 Hibás válasz 0/3 12ms 11664 KiB
17 Elfogadva 2/2 13ms 11896 KiB
18 Elfogadva 3/3 13ms 12004 KiB
19 Hibás válasz 0/2 13ms 12040 KiB
20 Hibás válasz 0/3 13ms 12096 KiB
21 Hibás válasz 0/2 12ms 12100 KiB
22 Elfogadva 3/3 12ms 12332 KiB