I was trying to figure this out on my own for some time but i could not so I need your help.

2072E - Do You Love Your Hero and His Two-Hit Multi-Target Attacks?

So the question wants you to find pairs where either |deltax| or |deltay| is zero. At first, i tried to find two numbers a and b such that a(a-1) / 2 + b(b-1) / 2 = k but there are numbers that are not a sum of two triangular numbers. Famously gauss proved that any number can be expressed as a sum of upto 3 triangular numbers a, b, c.

So this question boils down to find non-negative integers a, b, c such that a(a-1)/2 + b(b-1)/2 + c(c-1)/2 = k and a+b+c <= 500.

Since, k <= 10^5, a + b + c will be less than 500, because if we solve a(a-1) / 2 <= 10^5, we get a = 12 and following my code b will be 23 and c will be 447, hence 447 + 23 + 12 is 482 which is <= 500.

I implemented this below:

#include <bits/stdc++.h>

#define peace "\n"
#define ll long long
#define vi vector<int>
#define vl vector<long long>
#define vvi vector<vector<int>>
#define vvl vector<vector<long long>>

using namespace std;

const int MAXN = 1e5;

vi Tri;

vi bestl(MAXN+1, -1);
vi bestr(MAXN+1, -1);
vector<bool> hasrep(MAXN+1, false);

void precompute() {
    for (int i = 0; (i*(i-1)/2) <= MAXN; i++) {
        Tri.push_back(i*(i-1) / 2);
    }

    for (int l = 0; l < Tri.size(); l++) {
        for (int r = l; r < Tri.size(); r++) 
        {
            int s = Tri[l] + Tri[r];
            if (s > MAXN) break;
            if (!hasrep[s] || (l+r) < (bestl[s]+bestr[s])) {
                hasrep[s] = true;
                bestl[s] = l;
                bestr[s] = r;
            }
        }
    }
}

int main()
{
    precompute();

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while(t--)
    {
        int k; cin >> k;

        int a = -1, b = -1, c = -1;
        bool found = false;

        for (int i = 0; i < Tri.size(); i++) 
        {
            if (Tri[i] > k) break;
            int target = k - Tri[i];

            if (!hasrep[target]) continue;

            int l = bestl[target];
            int r = bestr[target];

            if (i + l + r <= 500) { 
                a = i;
                b = l;
                c = r;
                break; 
            }
        }

        cout << a + b + c << peace;

        for (int i = 0; i < a; i++) cout << (int)1e8 << " " << i << peace;
        for (int i = 0; i < b; i++) cout << (int)4e7 << " " << i + (int)1e4 << peace;
        for (int i = 0; i < c; i++) cout << i + (int)-1e4 << " " << (int)-1e8 << peace; 
    }
    return 0;
}

Its getting wrong answer on test case 5 with verdict wrong answer Integer parameter [name=n] equals to -3, violates the range [0, 500] (test case 11) Test Case 11 — k = 99011

Link to the submission — 378264114