#include <bits/stdc++.h>
#include <tuple>
using namespace std;
typedef long long ll;
typedef pair<ll , ll > pl;
typedef pair<int ,int > pa;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define endl '\n'
#define MP make_pair
#define PB push_back
#define p (ll)(1e9 + 7)
ll inv(ll i);
ll add(ll a, ll b) { return (a % p + b % p) % p; }
ll sub(ll a, ll b) { return (a % p - b % p) % p; }
ll mul(ll a, ll b) { return (a % p * b % p) % p; }
ll divm(ll a, ll b) { return mul(a, inv(b)); }
ll inv(ll i) { return i <= 1 ? i : p - (p / i) * inv(p % i) % p; }
ll ceil(ll a ,ll b)
{
ll x = a/b;
if(a%b !=0) x++;
return x;
}
ll power(ll a , ll b)
{
if(b==0) return 1;
ll x = power(a , b/2);
if(b%2 == 0) return x*x;
else return x*x*a;
}
ll log(ll a , ll b )
{
if(a/b > 0) return log(a/b , b) + 1;
else return 0;
}
//-------------------------------------------------------
//Instructions:-
//(1) Use a count array for once
//(2) Don't forget about the existence of 2 pointers :)
//(3) If subsequence of fixed number of elements is to be selected,sorted and using binary search may be a good idea
//(4) If nothing works, try to make a recursion for DP
//(5) Knapsack when u have to maximize one parameter(value) taking care of other(weight or cost), or finding all possibilites among subsequences
// -> the parameter must be of value and weights must be stored in array, which should be subracted till they are greater than 0, here dp[i] shows number of weights left after profit of i
// or
// -> the parameter must be of weights and profit must be stored in array, which should be added while index of weight must be subtracted,here dp[k] shows the minimum profit upon using weight k(not kth)
//(6) For O(n^2) , use smaller loop outside
//(7) We can find the number of operations like stuff ,with binary search for the answer and calling a boolean functionn of O(n) which tells if search should continue;
// -> bin(n){ find(n);}
// -> find(n){bin(n);}
// -> refer https://codeforces.com/contest/1843/problem/E
// (8) One more attempt, to try to binary search the answer, just find the function which needs to be optimized
// then binary search on the possible number of operations and optimizing the function may be in O(n + m) (o/w TLE)
// -> refer https://codeforces.com/contest/1843/problem/E
//For Usaco , put this in main
//if (fopen("file.in", "r")) {
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
//}
ll give(tuple<ll,ll,ll> a, int index)
{
if(index == 1)
return get<1>(a);
else if(index ==2)
return get<2> (a);
else return get<0> (a);
}
bool func(tuple<ll,ll,ll> a, tuple<ll,ll,ll> b)
{
double x = (double)(give(a, 0))/give(a,1);
double y = (double)(give(b, 0))/give(b,1);
return x > y;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll s, n;
cin >> s >> n;
tuple<ll, ll, ll> a[n];
for(int i = 0 ; i< n;i++)
{
ll x,y,z;
cin >> x >> y >> z;
a[i] = {x, y, z};
}
sort(a, a + n, func);
ll tot = 0;
ll ans = 0;
for(int i = 0 ; i< n;i++)
{
ll u = s - tot;
ll items = (u/give(a[i], 1));
if(items >= give(a[i], 2))
{
items = give(a[i], 2);
}
tot+=(items*give(a[i], 1));
ans +=(items*give(a[i], 0));
}
cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
324 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
324 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
324 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
324 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
