Grid Paths II

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

llu m1[N];
llu m2[N];

llu* a = m1;
llu* b = m2;

inline bool is_trap_fi(llu up, llu d) {
    llu y = d + 1;
    llu x = up - y + 1; 
    return traps.find(make_pair(x, y)) != traps.end();
}

inline bool is_trap_se(llu up, llu d, llu n) {
    llu y = n - up + d + 1;
    llu x = n - d;
    return traps.find(make_pair(x, y)) != traps.end();
}


llu g(llu n) {
    a[0] = 1;
    for (llu up = 1; up <= n ; ++up) {
        for (llu d = 0; d < up; ++d) {
            if (is_trap_se(up, d, n)) {
                b[d] = 0;
                continue;
            }

            if (d==0) {
                b[d] = a[d];
            } else if (d==up) {
                b[d] = a[d-1];
            }
            else {
                b[d] = a[d]+a[d-1];
            }
        }
        swap(a, b);
    }
    for (llu up = n - 1; up >= 1 ; --up) {
        for (llu d = 0; d < up; ++d) {
            if (is_trap_fi(up, d)) {
                b[d] = 0;
                continue;
            }
            b[d] = a[d]+a[d+1];
        }
        swap(a, b);
    }
    return a[0];
}


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(n);
    cout << result << endl;
    return 0;
}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

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