Submission #1188304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188304		alwaus424	Knapsack (NOI18_knapsack)	C++20	12 / 100	0 ms	328 KiB

knapsack

//In the name of ALLAH

#include<bits/stdc++.h>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


template < typename F, typename S >
ostream& operator << ( ostream& os, const pair< F, S > & p ) {
    return os << "(" << p.first << ", " << p.second << ")";
}

template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v ) {
    os << "{";
    for(auto it = v.begin(); it != v.end(); ++it) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "}";
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
template < typename T >
ostream &operator << ( ostream & os, const set< T > &v ) {
    os << "[";
    for(auto it = v.begin(); it != v.end(); ++it) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "]";
}

template < typename T >
ostream &operator << ( ostream & os, const multiset< T > &v ) {
    os << "[";
    for(auto it = v.begin(); it != v.end(); ++it) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "]";
}

template < typename F, typename S >
ostream &operator << ( ostream & os, const map< F, S > &v ) {
    os << "[";
    for(auto it = v.begin(); it != v.end(); ++it) {
        if( it != v.begin() ) os << ", ";
        os << it -> first << " = " << it -> second ;
    }
    return os << "]";
}

#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)

void faltu () {
    cerr << endl;
}

template <typename T>
void faltu( T a[], int n ) {
    for(int i = 0; i < n; ++i) cerr << a[i] << ' ';
    cerr << endl;
}

template <typename T, typename ... hello>
void faltu( T arg, const hello &... rest) {
    cerr << arg << ' ';
    faltu(rest...);
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
typedef long long ll;
const double PI = acos(-1);
const double eps = 1e-9;
const int inf = 2000000000;
const ll infLL = 9000000000000000000;
#define MOD 1000000007
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#define all(a) (a).begin(),(a).end()
#define sz(x) (int)x.size()
#define mid(l,r) ((r+l)/2)
#define left(node) (node*2)
#define right(node) (node*2+1)
#define mx_int_prime 999999937
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#define mem(a,b) memset(a, b, sizeof(a) )
#define gcd(a,b) __gcd(a,b)
#define sqr(a) ((a) * (a))
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fraction() cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# define vb vector <bool>
# define vc vector <char>
# define vs vector <string>
# define vvd vector < vector < double > >
# define vvld vector < vector < long double > >
# define pld pair < long double , long double >
# define pDD pair < double , double >
# define vpld vector < pld >
# define vpDD vector < pDD >
# define vvpii vector < vector < pii > >
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef double dl;
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#define srt(m) sort(m.begin(),m.end())
#define srtr(m) sort(m.rbegin(),m.rend())
#define rev(m) reverse(m.begin(),m.end())
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
#define fr(m) for(int i = 0; i < m; i++)
#define fro(m) for(int i=1; i<m; i++)
#define _ "\n"
#define nll cout << "\n";

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int dx[] = {0, 0, +1, -1};
int dy[] = {+1, -1, 0, 0};
//int dx[] = {+1, 0, -1, 0, +1, +1, -1, -1};
//int dy[] = {0, +1, 0, -1, +1, -1, +1, -1};
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
ll pow(ll a , ll b , ll m) {
    ll ans = 1 ;
    while(b) {
        if (b&1) {
            ans = (ans*a) % m ;
        }
        b /= 2 ;
        a = (a*a) % m ;
    }
    return ans ;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
const int MAXN = 1e6 + 5;
vector<bool> prime(MAXN, true);
void sieve() {
    prime[0] = prime[1] = false;
    for (int i = 2; i * i < MAXN;i++) {
        if (prime[i]) {
            for (int j = i * i; j < MAXN; j += i) {
                prime[j] = false;
            }
        }
    }
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
ll gcd(ll a, ll b) {
    if (b == 0) {
        return a ;
    }
    else {
        return gcd (b , a % b) ;
    }
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
ll lcm(ll a, ll b) {
    return ((a / gcd(a , b)) * b) ;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool rmDP(vector<int>& b, int target) {
    int n = b.size();
    vector<bool> dp(target + 1, false);
    vector<int> parent(target + 1, -1); // To track the last index used to make each sum
    dp[0] = true;

    for (int i = 0; i < n; ++i) {
        for (int j = target; j >= b[i]; --j) {
            if (dp[j - b[i]] && !dp[j]) {
                dp[j] = true;
                parent[j] = i;
            }
        }
    }

    if (!dp[target]) return false;

    // Backtrack to find indices to remove
    vector<int> used_indices;
    int curr = target;
    vector<bool> used(n, false);
    while (curr > 0 && parent[curr] != -1) {
        int idx = parent[curr];
        if (used[idx]) { // already used in this path
            return false;
        }
        used[idx] = true;
        used_indices.push_back(idx);
        curr -= b[idx];
    }

    // Remove used elements from b
    sort(used_indices.rbegin(), used_indices.rend());
    for (int idx : used_indices) {
        b.erase(b.begin() + idx);
    }

    return true;
}

void always424() {
    int s, n;
    cin >> s >> n;
    vector<tuple<int, int, int>> v(n);

    for (int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[i] = make_tuple(a, b, c);
    }

    ll tot = 0;   // Start from zero weight
    ll ans = 0;

    int cost = get<0>(v[0]);
    int weight = get<1>(v[0]);
    int quantity = get<2>(v[0]);

    while (quantity > 0 && tot + weight <= s) {
        tot += weight;
        ans += cost;
        quantity--;
    }

    cout << ans << '\n';
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main() {
    optimize();
    // sieve()
    auto start = chrono::high_resolution_clock::now();

    // ll t; cin >> t;
    // while(t--)
        always424();

    auto end = chrono::high_resolution_clock::now();
    cerr << "Time taken: " << chrono::duration<double>(end - start).count() << " seconds\n";

    return 0;
}

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