Cod sursa(job #87885)

Utilizator gigi_becaliGigi Becali gigi_becali Data 29 septembrie 2007 15:10:04
Problema Lapte Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <cstdio>
#include <string>
#define maxn 101

int n, S;
int dp[maxn][maxn], pi[maxn][maxn];
bool oki[maxn][maxn];

int a[maxn], b[maxn];

void read()
{
  freopen("lapte.in","r",stdin);
  scanf("%d %d\n", &n, &S);
  for(int i=1;i<=n;++i)scanf("%d %d\n", a+i, b+i);
}

inline int dynamic(int T)
{
  //   memset(dp, 0, sizeof(dp));
  //memset(pi, 0, sizeof(pi));
  //memset(oki, 0, sizeof(oki));
  int i, j, t;

  dp[0][0]=0;
  
  for(i=0;i<=n;++i)
    for(j=0;j<=S;++j)dp[i][j]=0, pi[i][j]=0, oki[i][j]=0;
  oki[0][0]=1;
  // for(i=0;i<=T;++i) dp[1][i]=(T-t*a[1])/b[1];
  // for(i=0;i<=T;++i) if(dp[1][i]<0) dp[1][i]=0;


  for(i=1;i<=n;++i)
    for(j=0;j<=S;++j)
      {
	   
	for(t=0; t*a[i]<=T && j-t>=0 && t<=S;++t)
	  {
	    if(j<t)break;
	    if(t>S)break;
	    if(t*a[i]>T)break;
	   
	     if(oki[i-1][j-t]) 
	      {
		//	 if(T==17){if(b[i]<=T) printf("%d %d %d\n",T-t*a[i],b[i], (T-t*a[i])/b[i]);}
		int r, q=(T-t*a[i])/b[i];
		if(b[i]==0) r=dp[i-1][j-t];
		else r=dp[i-1][j-t]+q;
		if(r>dp[i][j] && (t*a[i]+q*b[i]<=T))dp[i][j]=r, pi[i][j]=t,
		oki[i][j]=1;
	      }
	  }
      }
  /*  
 if(T==17)
    {
      for(i=1;i<=n;++i)
	{
	  for(j=0;j<=S;++j)printf("%d ", dp[i][j]);
	  printf("\n");
	}

    }
  */

  if(dp[n][S]>=S&& oki[n][S])return 1;
  return 0;
}

void afis(int i, int j, int T)
{
  if(i!=0)
    {
      afis(i-1, j-pi[i][j],T);
    
      int e=0;
      if(T-pi[i][j]*a[i]==0)e=0;
      else if(b[i]==0) e=0;
      else e=(T-pi[i][j]*a[i])/b[i];
 printf("%d %d\n", pi[i][j], e);
    }
}

void solve()
{
  int cnt, T;

  for(cnt=(1<<20), T=(1<<20); cnt ; cnt>>=1)
    if(T-cnt>=0)
      if(dynamic(T-cnt)) T-=cnt;

  //  printf("%d\n", dp[n][S]);
  //printf("%d\n", S);
  dynamic(T);
  printf("%d\n", T);
  afis(n, S, T);
}

int main()
{
  read();
  // solve();
    freopen("lapte.out","w",stdout);
    solve();
//  dynamic(18);
//    printf("%d\n", dynamic(17));
  return 0;
}