Fundamente XI - Etape - 213

#include <bits/stdc++.h>
#define pi pair < int , int >
#define x first
#define y second

using namespace std;

inline void Trace(int i, int j, vector < pi >& a, vector < vector < int > >& t) {
    if(t[i][j] != 0) {
        Trace(i - a[t[i][j]].x, j - a[t[i][j]].y, a, t);
        cout << a[t[i][j]].x << ' ' << a[t[i][j]].y << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, p, q;
    cin >> N >> p >> q;
    vector < pi > a(N + 1);
    for(int i = 1; i <= N; ++i)
        cin >> a[i].x >> a[i].y;
    vector < vector < int > > dp(128, vector < int >(128));
    /* dp[i][j] = x <=> exista o submultime de x meciuri in care gazdele au dat i goluri
       si oaspetii j */
    dp[a[1].x][a[1].y] = 1;
    vector < vector < int > > t(128, vector < int >(128));
    // t[i][j] = index-ul ultimului meci folosit pentru a obtine scorul (i, j)
    t[a[1].x][a[1].y] = 1;
    int x = a[1].x, y = a[1].y;
    for(int i = 2; i <= N; ++i) {
        for(int j = x; j >= 0; --j)
            for(int k = y; k >= 0; --k)
                if(dp[j][k] != 0 && dp[j + a[i].x][k + a[i].y] == 0) {
                    dp[j + a[i].x][k + a[i].y] = dp[j][k] + 1;
                    t[j + a[i].x][k + a[i].y] = i;
                }
        if(dp[a[i].x][a[i].y] == 0) {
            dp[a[i].x][a[i].y] = 1;
            t[a[i].x][a[i].y] = i;
        }
        x += a[i].x;
        y += a[i].y;
    }
    Trace(p, q, a, t);
}