Mixing Milk

Mixing Milk

Topic: Greedy

	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define MAX 10005
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	/*
	ID: hasanma1
	TASK: milk
	LANG: C++
	*/
	/* LANG can be C++11 or C++14 for those more recent releases */
	#include <iostream>
	#include <fstream>
	#include <string>
	using namespace std;
	int main() {
	FASTIO
	/*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	// /*
	ofstream cout ("milk.out");
	ifstream cin ("milk.in");
	//*/
	int n,m;
	cin >> n >> m;
	vector<pair<int, int> > v;
	for(int i = 0; i < m; i++){
	int p,a;
	cin >> p >> a;
	v.push_back({p,a});
	}
	sort(v.begin(), v.end());
	int ans = 0;
	for(int i = 0; i < m; i++){
	if(n <= 0) break;
	int mn = min(n, v[i].second);
	ans += (mn*v[i].first);
	n -= mn;
	}
	cout << ans << endl;
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw mixiingMilk(USACO).cpp hosted with ❤ by GitHub

Share: