mickypinata

TOCPC2021: Woody

Nov 23rd, 2021
78
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long lli;
  5.  
  6. const int N = 1000 + 5;
  7. const int X = 500 + 5;
  8.  
  9. int moveX[N], moveY[N], charge[N];
  10. lli dp[2][X][X];
  11.  
  12. int main(){
  13.  
  14.     int n, limX, limY;
  15.     scanf("%d%d%d", &n, &limX, &limY);
  16.     for(int i = 1; i <= n; ++i){
  17.         scanf("%d%d%d", &moveX[i], &moveY[i], &charge[i]);
  18.     }
  19.     int bcase = (n + 1) % 2;
  20.     dp[bcase][0][0] = 0;
  21.     for(int x = 1; x <= limX; ++x){
  22.         for(int y = 1; y <= limY; ++y){
  23.             dp[bcase][x][y] = 1e18;
  24.         }
  25.     }
  26.     for(int x = 1; x <= limX; ++x){
  27.         dp[bcase][x][0] = 1e18;
  28.     }
  29.     for(int y = 1; y <= limY; ++y){
  30.         dp[bcase][0][y] = 1e18;
  31.     }
  32.     for(int i = n; i >= 1; --i){
  33.         int cur = i % 2;
  34.         int nxt = cur ^ 1;
  35.         for(int x = 0; x <= limX; ++x){
  36.             for(int y = 0; y <= limY; ++y){
  37.                 if(x == 0 && y == 0){
  38.                     dp[cur][x][y] = 0;
  39.                     continue;
  40.                 }
  41.                 int rx = x - moveX[i] < 0 ? 0 : x - moveX[i];
  42.                 int ry = y - moveY[i] < 0 ? 0 : y - moveY[i];
  43.                 dp[cur][x][y] = min(dp[nxt][x][y], charge[i] + dp[nxt][rx][ry]);
  44.             }
  45.         }
  46.     }
  47.     if(dp[1][limX][limY] == 1e18){
  48.         cout << "-1";
  49.     } else {
  50.         cout << dp[1][limX][limY];
  51.     }
  52.  
  53.     return 0;
  54. }
  55.  
RAW Paste Data Copied