### Milk Scheduling

below given code is for msched spoj or milk scheduling spoj.

#include <stdio.h> #include <iostream> #include <cstdlib> #include <bitset> using namespace std; class job { public: int deadline; int profit; }; void mergesort(job a[],int low,int mid,int high) { job temp[10009]; int i=low,k=low,j=mid+1; while(i<=mid && j<=high) { if(a[i].profit >=a[j].profit) temp[k++]=a[i++]; else temp[k++]=a[j++]; } while(i<=mid) temp[k++]=a[i++]; while(j<=high) temp[k++]=a[j++]; for(i=low;i<=high;i++) a[i]=temp[i]; } void partition(job a[],int low,int high) { int mid; if(low<high) { mid=(low+high)/2; partition(a,low,mid); partition(a,mid+1,high); mergesort(a,low,mid,high); } } int main() { int n; scanf("%d",&n); int i,max=-1,k; bool p[10009]={0}; job j[n+9]; for(i=0;i<n;i++) { scanf("%d",&j[i].profit); scanf("%d",&j[i].deadline); } partition(j,0,n-1); int total=0,temp; for(i=0;i<n;i++) { temp=j[i].deadline; while(temp) { if(!p[temp]){ p[temp]=1; total+=j[i].profit; break; } else temp--; } } printf("%d",total); return 0; }