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

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

struct assist {
    int e,d;

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

const int inf=0x3f3f3f3f;

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

int doit(int i, int j) {
    if (i==n && j==0) return 0;
    if (i==n) return inf;

    if (dp[i][j]!=-1) return dp[i][j];

    int nhelp=doit(i+1,j)+p[i].e;
    int help=doit(i+1,j-1)+j*p[i].d;

    return dp[i][j]=min(nhelp,help);
}

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,-1,sizeof(dp));

        int np=-1;
        for (np=n; np>=0; np--)
            if (doit(0,np)<=k) break;

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