#include<stdio.h>
int p[]={1, 2, 3, 3, 4, 1, 2},
    d[]={2, 3, 3, 5, 7, 8, 8},
    w[]={2, 5,10, 3,17,10, 4},
    n=7;

int main(){
  int tmax=d[n-1];
  int f[n+1][tmax+1];
  int k,t;
  
  for(t=0;t<=tmax;t++) f[0][t]=0;
  
  for(k=0;k<n;k++)
  { for(t=0;t<=tmax;t++) f[k+1][t]=f[k][t];
    for(t=p[k];t<=d[k];t++)
    { int x=w[k]+f[k][t-p[k]];
      if(x>f[k][t]) f[k+1][t]=x;
    }
    for(t=d[k]+1;t<=tmax;t++) 
      if(f[k+1][t-1]>f[k][t])
        f[k+1][t]=f[k+1][t-1];
  }
  printf("Profit max : %d\n",f[n][tmax]);
  for(k=n,t=tmax; k; )
  if(k && f[k-1][t]==f[k][t]) k--; else
  if(t && f[k][t-1]==f[k][t]) t--; else
  k--, printf("La tâche %d exécutée de %d à %d donc avant la date %d rapporte %d\n", k, t-p[k], t, d[k], w[k]), t-=p[k];
  return 0;
}