18482022-12-05 08:37:39sztomiJegesmedve (50)cpp17Accepted 50/507ms4572 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";

}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/03ms1828 KiB
2Accepted0/02ms2072 KiB
3Accepted3/33ms2480 KiB
4Accepted3/33ms2728 KiB
5Accepted3/33ms3024 KiB
6Accepted4/44ms3604 KiB
7Accepted3/32ms2876 KiB
8Accepted3/32ms2952 KiB
9Accepted3/32ms3084 KiB
10Accepted4/42ms3288 KiB
11Accepted4/43ms3632 KiB
12Accepted4/43ms3580 KiB
13Accepted4/42ms3440 KiB
14Accepted4/44ms4052 KiB
15Accepted4/46ms4196 KiB
16Accepted4/47ms4572 KiB