TOCPC2021: Woody

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;

const int N = 1000 + 5;
const int X = 500 + 5;

int moveX[N], moveY[N], charge[N];
lli dp[2][X][X];

int main(){

    int n, limX, limY;
    scanf("%d%d%d", &n, &limX, &limY);
    for(int i = 1; i <= n; ++i){
        scanf("%d%d%d", &moveX[i], &moveY[i], &charge[i]);
    }
    int bcase = (n + 1) % 2;
    dp[bcase][0][0] = 0;
    for(int x = 1; x <= limX; ++x){
        for(int y = 1; y <= limY; ++y){
            dp[bcase][x][y] = 1e18;
        }
    }
    for(int x = 1; x <= limX; ++x){
        dp[bcase][x][0] = 1e18;
    }
    for(int y = 1; y <= limY; ++y){
        dp[bcase][0][y] = 1e18;
    }
    for(int i = n; i >= 1; --i){
        int cur = i % 2;
        int nxt = cur ^ 1;
        for(int x = 0; x <= limX; ++x){
            for(int y = 0; y <= limY; ++y){
                if(x == 0 && y == 0){
                    dp[cur][x][y] = 0;
                    continue;
                }
                int rx = x - moveX[i] < 0 ? 0 : x - moveX[i];
                int ry = y - moveY[i] < 0 ? 0 : y - moveY[i];
                dp[cur][x][y] = min(dp[nxt][x][y], charge[i] + dp[nxt][rx][ry]);
            }
        }
    }
    if(dp[1][limX][limY] == 1e18){
        cout << "-1";
    } else {
        cout << dp[1][limX][limY];
    }

    return 0;
}