Submission #522497

#	Time	Username	Problem	Language	Result	Execution time	Memory
522497		viethoangpham	Knapsack (NOI18_knapsack)	C++14	100 / 100	127 ms	11176 KiB

knapsack

#include<bits/stdc++.h>
#define faster  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define el "\n"
#define memset(a, x) memset(a, (x), sizeof(a));
#define sz(x) x.size()
#define pb push_back
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define mp make_pair
#define cont continue
using namespace std;
using ll = long long;
using ld = long double;
using str = string;
const int INF = int(1e9) + 100;
const ll MAXN = (1 << 20) + 55;
const ll MOD = 1e9 + 7;
#define yes cout << "yes" << el;
#define no cout << "no" << el;
#define umap unordered_map
ll pow_mod(ll a, ll b, ll m){ll res = 1;while (b){res = res * (b & 1 ? a : 1); res %= m;a *= a; a %= m;b >>= 1;}return res;}
ll gcd (ll x, ll y){return !y ? x : gcd(y, x % y);}
void setIn(str s) { freopen(s.c_str(),"r",stdin); }
void setOut(str s) { freopen(s.c_str(),"w",stdout); }
void setIO(str s) {
	setIn(s+".in"); setOut(s+".out");
}
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
ll n, s;
priority_queue <pair <ll, ll>> a[200005];
ll dp[300005];
main(){
    cin >> s >> n;
    for (int i = 0; i < n; i++){
        ll v, w, k; cin >> v >> w >> k;
        a[w].push({v, k});
    } 
    dp[0] = 0;
    for (int W = 1; W <= s; W++){
        ll k = s / W;
        while (!a[W].empty() && k){
            auto temp = a[W].top();
            a[W].pop();
            temp.se = min(temp.se, k);
            k -= temp.se;
            for (int i = 0; i < temp.se; i++){
                for (int j = s; j >= 1; j--){
                    if (j - W >= 0) dp[j] = max(dp[j], dp[j - W] + temp.fi); 
                }
            }
        }
    }
    cout << dp[s] << el;
}

Compilation message (stderr)

knapsack.cpp:34:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   34 | main(){
      | ^~~~
knapsack.cpp: In function 'void setIn(str)':
knapsack.cpp:24:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 | void setIn(str s) { freopen(s.c_str(),"r",stdin); }
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
knapsack.cpp: In function 'void setOut(str)':
knapsack.cpp:25:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 | void setOut(str s) { freopen(s.c_str(),"w",stdout); }
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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