USACO : Mixing Milk

Problem Link : http://train.usaco.org/usacoprob2?a=ZjtQpZMHmbg&S=milk


/*
PROG: milk
LANG: C++
*/

#include <bits/stdc++.h>

#define pii pair <int,int>
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 10000
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#define getint2(a,b) scanf("%d%d",&a,&b)
#define getint3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define loop(i,n) for(int i=0;i<n;i++)
#define TEST_CASE(t) for(int z=1;z<=t;z++)
#define PRINT_CASE printf("Case %d: ",z)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 1000000
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int

using namespace std;
vector<pii>v;

int main()
{
    freopen("milk.in","r",stdin);
    freopen("milk.out","w",stdout);
    int n,m,ans=0,a,b;
    getint2(n,m);
    loop(i,m)
    {
        getint2(a,b);
        v.pb(MP(a,b));
    }
    
    sort(all(v));

    for(int i=0;i<SZ(v);i++)
    {
        if(n==0)
            break;
        if(n<=v[i].ss)
        {
            ans+=(n*v[i].ff);
            break;
        }
        else
        {
            ans+=(v[i].ss*v[i].ff);
            n-=v[i].ss;
        }
    }
    cout<<ans<<endl;
    v.clear();
    return 0;
}


Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s