1848 2022. 12. 05 08:37:39 sztomi Jegesmedve (50) cpp17 Elfogadva 50/50 7ms 4572 KiB
#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9 + 7;

typedef pair<int, int> pii;

int n, m;
int sor_valt[4]{0, 0, 1, -1};
int oszlop_valt[4]{1, -1, 0, 0};

vector<vector<int>> olvadas;
vector<vector<int>> hal;
vector<vector<int>> fa;

struct comp{
    bool operator()(pii a, pii b){
        return a.first < b.first;
    }
};

int ind(pii kord){
    return kord.first*m + kord.second;
}

pii kord(int ind){
    return {ind/m, ind-ind/m*m};
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    olvadas.assign(n, vector<int>(m));
    hal.assign(n, vector<int>(m));
    pii start;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> olvadas[i][j];
            if(olvadas[i][j] == -1){
                start = {i, j};
            }
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> hal[i][j];
        }
    }

    fa.assign(n*m, vector<int>());
    vector<bool> faban(n*m, false);
    priority_queue<pii, vector<pii>, comp> pq;
    pq.push(make_pair(INF, ind(start)));

    map<int, int> db;

    pii akt;
    while(!pq.empty()){
        akt = pq.top();
        pq.pop();
        faban[akt.second] = true;

        pii hely = kord(akt.second);
        //cout << akt.first << " " << hal[hely.first][hely.second] << " " << akt.second << "\n";
        db[akt.first] += hal[hely.first][hely.second];

        for(int i = 0; i < 4; i++){
            pii uj = {hely.first + sor_valt[i], hely.second + oszlop_valt[i]};

            if(uj.first < 0 || uj.first >= n) continue;
            if(uj.second < 0 || uj.second >= m) continue;
            if(faban[ind(uj)]) continue;

            int ertek = min(olvadas[uj.first][uj.second], akt.first);
            faban[ind(uj)] = true;
            pq.push(make_pair(ertek, ind(uj)));
            fa[akt.second].push_back(ind(uj));
        }
    }

    int ki = 0;
    for(auto x : db){
        ki += min(x.first - ki + 1, x.second);
    }
    cout << ki << "\n";

}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1828 KiB
2 Elfogadva 0/0 2ms 2072 KiB
3 Elfogadva 3/3 3ms 2480 KiB
4 Elfogadva 3/3 3ms 2728 KiB
5 Elfogadva 3/3 3ms 3024 KiB
6 Elfogadva 4/4 4ms 3604 KiB
7 Elfogadva 3/3 2ms 2876 KiB
8 Elfogadva 3/3 2ms 2952 KiB
9 Elfogadva 3/3 2ms 3084 KiB
10 Elfogadva 4/4 2ms 3288 KiB
11 Elfogadva 4/4 3ms 3632 KiB
12 Elfogadva 4/4 3ms 3580 KiB
13 Elfogadva 4/4 2ms 3440 KiB
14 Elfogadva 4/4 4ms 4052 KiB
15 Elfogadva 4/4 6ms 4196 KiB
16 Elfogadva 4/4 7ms 4572 KiB