Submission #522476

#	Time	Username	Problem	Language	Result	Execution time	Memory
522476		viethoangpham	Knapsack (NOI18_knapsack)	C++14	73 / 100	342 ms	262148 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;
ll w[2000000], v[2000000], k[2000000];
ll dp[2001];
vector <pair <ll, ll>> a;
priority_queue <ll> pro[200005];
main(){
    cin >> s >> n;
    for (int i = 0; i < n; i++){
        cin >> v[i] >> w[i] >> k[i];
        k[i] = min(k[i], s / w[i]);
        while (k[i]--) pro[w[i]].push(v[i]);
    }
    for (int i = 1; i <= s; i++){
        ll cnt = s / i;
        if (!pro[i].size()) cont;
        while (cnt-- && !pro[i].empty()){
            ll V = pro[i].top();
            pro[i].pop();
            a.pb({V, i});
        }
    }
    dp[0] = 0;
    for (int i = 0; i < a.size(); i++){
        ll V = a[i].fi, W = a[i].se;
        for (int j = s; j >= 1; j--){
            if (j - W >= 0) dp[j] = max(dp[j], dp[j - W] + V);
        }
    }
    cout << dp[s] << el;
}

Compilation message (stderr)

knapsack.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | main(){
      | ^~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (int i = 0; i < a.size(); i++){
      |                     ~~^~~~~~~~~~
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: 0 / 27