Submission #684491

#	Time	Username	Problem	Language	Result	Execution time	Memory
684491		steamEngine	Knapsack (NOI18_knapsack)	C++17	100 / 100	195 ms	248064 KiB

knapsack

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimize("unroll-loops")
#include "bits/stdc++.h"

/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define node pair<int,int>
#define ordered_set tree<node, null_type,less<node>, rb_tree_tag,tree_order_statistics_node_update>

    //order_of_key (k) : Number of items strictly smaller than k
    //find_by_order(k) : K-th element in a set (counting from zero)

*/
#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define ff              first
#define endl            '\n'
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define fr(i, s, e) for(int i = s; i < e; i++)
#define rfr(i, s, e) for(int i = s; i >= e; i--)
#define geta(a, n) for(int i = 0; i < n; i++) cin >> a[i];
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define all(x) x.begin(),x.end()


#define MOD 1000000007
using namespace std;
using ll = long long;
vi init(string s)
{
    istringstream sin(s);
    int n;
    vi arr;
    while (sin >> n)arr.push_back(n);
    return arr;
}
// int dx[]={-1,1,0,0}; int dy[]={0,0,1,-1};
// int dx[]={2,2,-2,-2,1,1,-1,-1}; int dy[]={1,-1,1,-1,2,-2,2,-2};

/*------------------------------UNORDERED MAP HASH --------------------------------------------*/
//To make unordered_map unhackable
// use it as unordered_map<int,int,custom_hash> mapp;
/*
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
*/
/*------------------------------END--------------------------------------------*/
inline int powMod(int a, int b) { int x = 1; while (b > 0) { if (b & 1) x = (x * a) % MOD; a = (a * a) % MOD; b >>= 1; } return x; }
inline int multiply(int x, int y) { return ((x % MOD) * (y % MOD)) % MOD; }
inline int divide(int x, int y) { return ((x % MOD) * powMod(y % MOD, MOD - 2)) % MOD; }
inline int ceil(int a, int b) { return (a + b - 1) / b; }
int gcd (int a, int b) { while (b) { a %= b; swap(a, b); } return a; }
int lcm (int a, int b) { return a / gcd(a, b) * b; }
int inverseMod(int a, int m) { a = a % m; for (ll x = 1; x < m; x++) if ((a * x) % m == 1) return x; return -1; }
/* DEBUGGING */
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;


#ifndef ONLINE_JUDGE

#define debug(x)       \
    cerr << #x << " "; \
    _print(x);         \
    cerr << endl;

#else
#define debug(x)

#endif


void _print(ll t)
{
    cerr << t;
}

void _print(string t)
{
    cerr << t;
}
void _print(char t)
{
    cerr << t;
}
void _print(lld t)
{
    cerr << t;
}
void _print(double t)
{
    cerr << t;
}
void _print(ull t)
{
    cerr << t;
}

template <class T, class V>
void _print(pair<T, V> p);
template <class T>
void _print(vector<T> v);
template <class T>
void _print(set<T> v);
template <class T, class V>
void _print(map<T, V> v);
template <class T>
void _print(multiset<T> v);
template <class T, class V>
void _print(pair<T, V> p)
{
    cerr << "{";
    _print(p.ff);
    cerr << ",";
    _print(p.ss);
    cerr << "}";
}
template <class T>
void _print(vector<T> v)
{
    cerr << "[ ";
    for (T i : v)
    {
        _print(i);
        cerr << " ";
    }
    cerr << "]";
    cerr << "\n";
}
template <class T>
void _print(set<T> v)
{
    cerr << "[ ";
    for (T i : v)
    {
        _print(i);
        cerr << " ";
    }
    cerr << "]";
    cerr << "\n";
}
template <class T>
void _print(multiset<T> v)
{
    cerr << "[ ";
    for (T i : v)
    {
        _print(i);
        cerr << " ";
    }
    cerr << "]";
    cerr << "\n";
}
template <class T, class V>
void _print(map<T, V> v)
{
    cerr << "[ ";
    for (auto i : v)
    {
        _print(i);
        cerr << " ";
    }
    cerr << "]";
    cerr << "\n";
}
void print(vector<int> &arr) {
    for (auto &i : arr) cout << i << " ";
    cout << endl;
}
void print(string s) {
    cout << s << endl;
}
/* END DEBUGGING */
template<int D, typename T> struct vec : public vector < vec < D - 1, T >> { static_assert(D >= 1, "Vector dimension must be greater than zero!");  template<typename... Args> vec(int n = 0, Args... args) : vector < vec < D - 1, T >> (n, vec < D - 1, T > (args...)) { } }; template<typename T> struct vec<1, T> : public vector<T> { vec(int n = 0, T val = T()) : vector<T>(n, val) { }};

bool comp(pair<int,int> &a,pair<int,int> &b){
    return a.ff>b.ff;
}
void solve() {
    int s,n;
    cin>>s>>n;
    // vi wi ki
    map<int,vector<pair<int,int>> > hash;
    for(int i=0;i<n;i++){
        int v,w,k;
        cin>>v>>w>>k;
        hash[w].push_back({v,k});

    } 
    vector<int> value,weight;
    for(auto &p:hash)
    {
        int w=p.ff;
        auto v=p.ss;
        int req=s/w;
        int rem=req;
        sort(all(v),comp);
        for(auto &x:v){
            if(rem==0) break;
            int current=min(x.ss,rem);
            rem-=current;
            while(current--){
                weight.pb(w);
                value.pb(x.ff);
            }
        }
    }
    // debug(weight);
    // debug(value);
    vector<vector<int>> dp(weight.size()+1,vector<int>(s+1,0));
    for(int i=1;i<dp.size();i++){
        // debug("yo");
        // debug(i);
        for(int j=1;j<=s;j++){
            dp[i][j]=dp[i-1][j];
            // debug(i);
            // debug(j);
            if((j-weight[i-1])>=0) dp[i][j]=max(dp[i][j],value[i-1]+dp[i-1][j-weight[i-1]]);
            // debug("hmm");
        }
    }    
    // debug(dp);
    // debug("hello");
    cout<<dp[weight.size()][s];
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif
    int t = 1;
    // cin >> t;
    while (t--) solve();

    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:240:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  240 |     for(int i=1;i<dp.size();i++){
      |                 ~^~~~~~~~~~
knapsack.cpp: In function 'int32_t main()':
knapsack.cpp:264:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  264 |     freopen("error.txt", "w", stderr);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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