Help-or-else O(n^2) iterativo AC - Live Archive 5688

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;

struct assist {
    int d,e;

    bool operator<(const assist& a) const {
        return this->d<a.d;
    }
};

const int inf=0x3f3f3f3f;

int n,k;
int dp[210][210];
assist p[210];
int _42=1;

int main() {
    while (1) {
        scanf("%d %d", &n,&k);
        if (!n && !k) break;

        for (int i=0; i<n; i++)
            scanf("%d %d", &p[i].e, &p[i].d);
        sort(p,p+n);

        memset(dp,0x3f,sizeof(dp));

        for (int i=0; i<=n; i++)
            dp[i][0]=0;

        for (int i=n-1; i>=0; i--)
            for (int j=0; j<=n; j++) {
                dp[i][j]=dp[i+1][j]+p[i].e;
                if (j) dp[i][j]=min(dp[i][j],
                    dp[i+1][j-1]+p[i].d*j);
            }

        int np;
        for (np=n; np>=0; np--)
            if (dp[0][np]<=k) break;

        if (np==-1)
            printf("%d: Mission Impossible\n", _42++);
        else
            printf("%d: %d\n", _42++, np);
    }
    return 0;
}