Apartments

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

bool dfs(vector<bool> &visited, vector<vector<int>>&g, vector<int> & match, int node){
    for (int next: g[node]){
        if (visited[next]){
            continue;
        }
        visited[next]=true;
        if (match[next]==-1 || dfs(visited, g, match, match[next])){
            match[next]=node;
            return true;
        }


    }
    return false;
}



int main(){

    int n, m, k;

    cin >> n >> m >> k;

    vector<int> applicants(n);
    vector<int> apartments(m);
    vector<int> match(m, -1);


    for (int i=0;i<n;i++){
        cin >> applicants[i];
    }

    for (int j=0;j<m;j++){
        cin >> apartments[j];
        match[j]=-1;
    }

    vector<vector<int>> g(n, vector<int>(0));


    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            if (applicants[i]>=apartments[j]-k && applicants[i]<=apartments[j]+k){
                g[i].push_back(j);
            }
        }
    }
    int matches=0;
    for(int i=0;i<n;i++){

        vector<bool> visited(m);
        if (dfs(visited, g, match, i)) {
            matches++;
        }
    }

    cout << matches << '\n';


}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: TIME LIMIT EXCEEDED

Test 14

Verdict: TIME LIMIT EXCEEDED

Test 15

Verdict: TIME LIMIT EXCEEDED

Test 16

Verdict: TIME LIMIT EXCEEDED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED