Submission #788478

#	Time	Username	Problem	Language	Result	Execution time	Memory
788478		Dikshant2004	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	324 KiB

knapsack

#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;
}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27