Cod sursa(job #2541686)

Utilizator ivddabDabelea Ioana-Viviana ivddab Data 8 februarie 2020 18:39:51
Problema Lapte Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define NM 105
#define oo 2e9
using namespace std;
ifstream f("lapte.in");
ofstream g("lapte.out");
int n,l,st,dr,mijl,i,rasp;
int  a[NM],b[NM];
int d[NM][NM],bk[NM][NM];
pair < int,int > r[NM];
int verif(int t){
  int i,j,k;
  for(i=0;i<=n;i++)
   for(j=0;j<=l;j++)
    d[i][j]=-oo;
  d[0][0]=0;
  for(i=1;i<=n;i++)
    for(j=0;j<=l;j++)
     for(k=0;k<=j&&k*a[i]<=t;k++){
        int x;
        x=(t-k*a[i])/b[i];
        if(d[i][j]<d[i-1][j-k]+x){
            bk[i][j]=j-k;
            d[i][j]=d[i-1][j-k]+x;
        }
     }
  if(d[n][l]>=l) return 1;
  return 0;
}
int main()
{
    f>>n>>l;
    for(i=1;i<=n;i++)
      f>>a[i]>>b[i];

    st=1; dr=105;
    while(st<=dr){
        mijl=(st+dr)/2;
        if(verif(mijl)==1){
            rasp=mijl;
            dr=mijl-1;
        } else st=mijl+1;
    }

    verif(rasp);
    int x=n;
    while(n!=0){
        r[n].first=l-bk[n][l];
        r[n].second=d[n][l]-d[n-1][bk[n][l]];
        l=bk[n][l]; n--;
    }
    g<<rasp<<'\n';
    for(i=1;i<=x;i++) g<<r[i].first<<' '<<r[i].second<<'\n';
    return 0;
}