Submission #640336

#	Time	Username	Problem	Language	Result	Execution time	Memory
640336		htphong0909	Knapsack (NOI18_knapsack)	C++17	73 / 100	1088 ms	2676 KiB

knapsack

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "O3")

using namespace std;

///Loops
#define fow(i,start,end,step) for(ll i = (start); i <= (end); i += (step))
#define rep(i,start,end,step) for(ll i = (start); i < (end); i+= (step))
#define dow(i,start,end,step) for(ll i = (start); i >= (end); i-= (step))
///Others
#define FASTIO ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define reset(a, val) memset(a, val, sizeof(a))
#define SQR(a) (1LL)*(a)*(a) // a * a
#define BIT(a) (1 << (a)) // 2^a
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define MAX 500500
///Read File
void setIO(const string &NAME = ""){
    if ((int) NAME.length() && fopen((NAME + ".inp").c_str(), "r")) {
        freopen((NAME + ".inp").c_str(), "r", stdin),
        freopen((NAME + ".out").c_str(), "w", stdout);
    }
}
///Sort & Remove Duplicate
void ReDup(vector<int> &v){
    sort(all(v)); v.erase(unique(all(v)), v.end());
}
///Minimize a = min(a, b)
template<class X, class Y> bool ckmin(X &x, const Y &y) {
        X eps = 1e-9;
        if (x > y + eps) {
            x = y;
            return true;
        } else return false;
    }
///Maximize a = max(a, b)
template<class X, class Y> bool ckmax(X &x, const Y &y) {
        X eps = 1e-9;
        if (x + eps < y) {
            x = y;
            return true;
        } else return false;
    }
using ll = long long;
using lli = long long int;
using ulli = unsigned long long int;
using db = double;
using fl = float;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using mii = map<int, int>;
using msi = map<string, int>;

const int MOD = (int) 1e9 + 7; //998244353;
const int inf = (int) 1e9 + 7;
const ll INF = 1e18;
/** END OF TEMPLATE **/
ll times;

ll w[10000001],v[10000001], a[10000001], l[10000100];
void solve(){
    ll n, m;
    ll mins = inf;
    cin >> m >> n;

    fow(i, 1, n, 1) cin >> v[i] >> w[i] >> a[i];

    fow(i, 1, m, 1) l[i] = 0;

    fow(i, 1, n, 1){
        dow(j, m, w[i], 1){
            mins = min(a[i], j / w[i]);
            fow(k, 0, mins, 1){
                ckmax(l[j],l[j - w[i]*k] + v[i]*k);
            }
        }
    }
    cout << l[m];
}

signed main(){
    FASTIO;
    //cin >> times;
    times = 1;
    while(times > 0){
        solve();
        times--;
    }
}

Compilation message (stderr)

knapsack.cpp: In function 'void setIO(const string&)':
knapsack.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen((NAME + ".inp").c_str(), "r", stdin),
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen((NAME + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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