UVALive 6042 Bee Tower

#include  
#include  
#include  
#include  
#include  
#include  
#define LL long long  
#define CLR(a, b) memset(a, b, sizeof(a))  
  
using namespace std;  
const int N = 111;  
const int W = 555;  
const int INF = 0X3f3f3f3f;  
  
struct Power  
{  
    int p, h;  
} pw[N];  
  
int dp[N][W], h, w;  
  
int solvel(int s, int e)  
{  
    int ret = INF;  
    if(pw[s].h <= h) return 0;  
    dp[s][pw[s].p] = 0;  
    for(int i = s - 1; i >= e; i --)  
    {  
        if(pw[i + 1].h - pw[i].h > h) return INF;  
        for(int j = pw[s].p - (s - i - 1); j >= pw[s].p - (s - i - 1) * w; j --)  
        {  
            if(j > 0)for(int k = j - 1; k >= j - w; k --)  
            {  
                dp[i][k] = min(dp[i][k], dp[i + 1][j] + abs(pw[i].p - k) * pw[i].h);  
                if(pw[i].h <= h) ret = min(ret, dp[i][k]);  
            }  
        }  
    }  
    return ret;  
}  
  
int solver(int s, int e)  
{  
    int ret = INF;  
    dp[s][pw[s].p] = 0;  
    if(pw[s].h <= h) return 0;  
    for(int i = s + 1; i <= e; i ++)  
    {  
        if(pw[i - 1].h - pw[i].h > h) return INF;  
        for(int j = pw[s].p + (i - s - 1); j <= pw[s].p + (i - s - 1) * w; j ++)  
        {  
            if(j >





 0)for(int k = j + 1; k <= j + w; k ++)  
            {  
                dp[i][k] = min(dp[i][k], dp[i - 1][j] + abs(pw[i].p - k) * pw[i].h);  
                if(pw[i].h <= h) ret = min(ret, dp[i][k]);  
            }  
        }  
        if(pw[i].h <= h) break;  
    }  
    return ret;  
}  
  
vector ca;  
  
int main()  
{  
    int t, n, sit, hh, ans, cas = 1;  
    scanf("%d", &t);  
    while(t --)  
    {  
        scanf("%d%d%d", &n, &h, &w);  
        hh = 0;  
        ca.clear();  
        for(int i = 1; i <= n; i ++)  
        {  
            scanf("%d%d", &pw[i].p, &pw[i].h);  
            if(pw[i].h > hh)  
            {  
                hh = pw[i].h;  
                ca.clear();  
                ca.push_back(i);  
            }  
            else if(pw[i].h == hh) ca.push_back(i);  
        }  
        CLR(dp, INF);  
        ans = INF;  
        for(int i = 0; i < ca.size(); i ++)  
        {  
            ans = min(ans, solvel(ca[i], 1));  
            ans = min(ans, solver(ca[i], n));  
        }  
        if(ans == INF) ans = -1;  
        printf("Case #%d: %d\n", cas ++, ans);  
    }  
}