http://acm.pku.edu.cn/JudgeOnline/problem?id=1018

Код:
#include <stdio.h>
#include <string.h>
#define MAXN 10010

int f[2][MAXN];
int dev[MAXN];
int task;
int n,m,t;

int main()
{
    int i,j,k,l,p,q;
    float h;
    scanf("%d",&task);
    while (task--)
    {
        scanf("%d",&n);
        memset(f,-1,sizeof(f));
        dev[0] = 2147473647;
        f[0][0] = 0; t = 0;
        for (i = 1; i <= n; i++)
        {
            scanf("%d",&m);
            p = t;
            for (j = 1; j <= m; j++)
            {
                 t++;
                 scanf("%d%d",&dev[t],&k);
                 for (l = 0; l <= p; l++)
                 {
                     if (f[0][l] == -1) continue;
                     if (dev[l] > dev[t]) q = t;
                     else q = l;
                     if (f[0][l] + k < f[1][q] || f[1][q] == -1)
                     f[1][q] = f[0][l] + k;
                 }
            }
            memcpy(f[0],f[1],sizeof(f[0]));
            memset(f[1],-1,sizeof(f[1]));
       }
       h = 0;
       for (i = 0; i <= t; i++)
       if (f[0][i] > -1)
       if ((float)dev[i] / (float)f[0][i] > h)
       h = (float)dev[i] / (float)f[0][i];
       printf("%.3f\n",h);
   }
   return 0;
}