Grid Paths II

#include <iostream>
#include <algorithm>
#include <string>
#include <bits/stdc++.h>
#define N 1000
using namespace std;
using llu = long long unsigned;
map<pair<llu, llu>, llu> m;
map<pair<llu, llu>, llu> traps;



llu g(llu xi, llu yi, llu n) {
    m[make_pair(n,n)] = 1;
    llu r=2*n;

    for (llu i = r; i > 1; i--) {
        for (llu x = i-1; x > 0; x--) {
            if (1>x or x > n)
                continue;
            llu y = i - x;
            if (1>y or y > n)
                continue;
            if (x == n and y == n)
                continue;

            if (traps.find(make_pair(x, y)) != traps.end()){
                m[make_pair(x, y)] = 0;
                continue;
            }

            llu a=0;
            llu b=0;
            if (m.find(make_pair(x+1, y)) == m.end()) {
                a=0;
            }else {
                a = m[make_pair(x+1,y)];
            }

            if (m.find(make_pair(x, y+1)) == m.end()) {
                b=0;
            }else {
                b= m[make_pair(x,y+1)];
            }

            m[make_pair(x, y)] = (a+b) % (1000000000 + 7);
        }
    }

    return m[make_pair(1,1)];

}


int main()
{
    llu n, traplen;

    cin >> n >> traplen;

    for (llu i = 0; i < traplen; i++ ) {
        llu a, b;
        cin >> a >> b;
        traps[make_pair(a,b)] = 1;
    }
    llu result = g(1, 1, n);
    cout << result << endl;
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED