18472022-12-05 08:26:45sztomiJegesmedve (50)cpp17Hibás válasz 3/507ms5040 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();
        faban[akt.second] = true;
        db[akt.first]++;
        pq.pop();

        pii hely = kord(akt.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ÖsszpontTesztVerdiktIdőMemória
base3/50
1Elfogadva0/03ms1824 KiB
2Hibás válasz0/02ms2080 KiB
3Elfogadva3/33ms2488 KiB
4Hibás válasz0/33ms2740 KiB
5Hibás válasz0/34ms2992 KiB
6Hibás válasz0/44ms3564 KiB
7Hibás válasz0/32ms3068 KiB
8Hibás válasz0/32ms3544 KiB
9Hibás válasz0/32ms3420 KiB
10Hibás válasz0/42ms3516 KiB
11Hibás válasz0/43ms3880 KiB
12Hibás válasz0/43ms3676 KiB
13Hibás válasz0/43ms3780 KiB
14Hibás válasz0/44ms4336 KiB
15Hibás válasz0/46ms4608 KiB
16Hibás válasz0/47ms5040 KiB