22362023-01-04 16:38:35TuruTamasJegesmedve (50)cpp11Runtime error 23/50400ms63544 KiB
#include <bits/stdc++.h>
using namespace std;

void bejar2(vector<vector<int>> tabla, pair<int , int> kezd, int nap, int N, int M, int** olvad, int** volt) {
    volt[kezd.first][kezd.second] = nap;
    if (olvad[kezd.first][kezd.second] < nap) {
        olvad[kezd.first][kezd.second] = nap;
    }
    if (kezd.first != 0 && volt[kezd.first - 1][kezd.second] < nap) {
        bejar2(tabla, pair<int,int>(kezd.first - 1, kezd.second), min(nap, tabla[kezd.first - 1][kezd.second]), N, M, olvad, volt);
    } // fel
    if (kezd.first != N - 1 && volt[kezd.first + 1][kezd.second] < nap) {
        bejar2(tabla, pair<int,int>(kezd.first + 1, kezd.second), min(nap, tabla[kezd.first + 1][kezd.second]), N, M, olvad, volt);
    } // le
    if (kezd.second != 0 && volt[kezd.first][kezd.second - 1] < nap) {
        bejar2(tabla, pair<int,int>(kezd.first, kezd.second - 1), min(nap, tabla[kezd.first][kezd.second - 1]), N, M, olvad, volt);
    } // balra
    if (kezd.second != M - 1 && volt[kezd.first][kezd.second + 1] < nap) {
        bejar2(tabla, pair<int,int>(kezd.first, kezd.second + 1), min(nap, tabla[kezd.first][kezd.second + 1]), N, M, olvad, volt);
    } // jobbra
}

int main() {
    int N, M; cin >> N >> M;
    vector<vector<int>> tabla;
    vector<vector<int>> halak;
    pair<int, int> medve;
    set<int> napok;
    for (int i = 0; i < N; i++)
    {
        vector<int> tmp;
        for (int k = 0; k < M; k++)
        {
            int x; cin >> x;
            if (x == -1) {
                medve.first = i;
                medve.second = k;
            }
            napok.insert(x);
            tmp.push_back(x);
        }
        tabla.push_back(tmp);
    }
    for (int i = 0; i < N; i++)
    {
        vector<int> tmp;
        for (int k = 0; k < M; k++)
        {
            int x; cin >> x;
            tmp.push_back(x);
        }
        halak.push_back(tmp);
    }
    vector<int> napok_halak;
    {
    int ** olvad = new int*[N];
    for (int i = 0; i < N; i++)
    {
        olvad[i] = new int[M];
        fill(olvad[i], olvad[i] + M, -1);
    }
    int ** volt = new int*[N];
    for (int i = 0; i < N; i++)
    {
        volt[i] = new int[M];
        fill(volt[i], volt[i] + M, -1);
    }
    if (medve.first != 0) {
        bejar2(tabla, pair<int, int> (medve.first - 1, medve.second), tabla[medve.first - 1][medve.second], N, M, olvad, volt);
    }
    if (medve.first != N - 1) {
        bejar2(tabla, pair<int, int> (medve.first + 1, medve.second), tabla[medve.first + 1][medve.second], N, M, olvad, volt);
    }
    if (medve.second != 0) {
        bejar2(tabla, pair<int, int> (medve.first, medve.second - 1), tabla[medve.first][medve.second - 1], N, M, olvad, volt);
    }
    if (medve.second != M - 1) {
        bejar2(tabla, pair<int, int> (medve.first, medve.second + 1), tabla[medve.first][medve.second + 1], N, M, olvad, volt);
    }

    olvad[medve.first][medve.second] = *(--napok.end());
    
    napok_halak.resize(*(--napok.end()) + 1);
    fill_n(napok_halak.begin(), napok_halak.size(), 0);
    for (int i = 0; i < N; i++)
    {
        for (int k = 0; k < M; k++)
        {
            napok_halak[olvad[i][k]] += halak[i][k];
        }
    }
    }
    int nap = 0;
    for (int i = 0; i < napok_halak.size(); i++)
    {
        nap = min(napok_halak[i] + nap, i);
    }
    
    cout << nap + 1 << endl;
    
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base23/50
1Accepted0/03ms1812 KiB
2Accepted0/04ms2880 KiB
3Accepted3/316ms19416 KiB
4Accepted3/335ms46800 KiB
5Runtime error0/328ms62900 KiB
6Runtime error0/435ms62852 KiB
7Accepted3/33ms3544 KiB
8Accepted3/33ms3544 KiB
9Accepted3/33ms3800 KiB
10Accepted4/43ms3748 KiB
11Time limit exceeded0/4400ms17848 KiB
12Time limit exceeded0/4365ms11084 KiB
13Accepted4/4293ms16976 KiB
14Runtime error0/434ms63544 KiB
15Runtime error0/434ms63328 KiB
16Runtime error0/439ms63092 KiB