Submission #682814

#	Time	Username	Problem	Language	Result	Execution time	Memory
682814		DeMen100ns	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	372 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

//debug
#define dbg(a) cout << #a << " : " << a << endl;
#define dbga(a, l, r) cout << #a << " : "; for(long long abc = l; abc <= r; ++abc) cout << a[abc] << " "; cout << endl
#define dbgv(a) cout << #a << " : "; for(auto abc: a) cout << abc << " "; cout << endl

//Finite Field
const int MOD = 1e9 + 7;
void add(int &a, int b, int mod = MOD){ a += b; while (a < 0) a += mod; while (a >= mod) a -= mod; }
int sum(int a, int b, int mod = MOD){ return add(a, b, mod), a; }
void mul(int &a, int b, int mod = MOD){ a = (a * 1LL * b) % mod; }
int prod(int a, int b, int mod = MOD){ return mul(a, b, mod), a; }
int bpow(int a, int b, int mod = MOD){ int ans = 1; while (b){ if (b & 1){ mul(ans, a, mod); } mul(a, a, mod); b >>= 1; } return ans; }
int Inv(int a, int mod = MOD){ return bpow(a, mod - 2, mod); }
int Div(int a, int b, int mod = MOD) { return prod(a, Inv(b, mod), mod); }

const int N = 2e5 + 5;
const long long INF = numeric_limits<long long>::max() / 2;
const int MAXA = 1e9;
const int B = sqrt(N) + 5;

int v[N], w[N], k[N];
int dp[2005];

vector <int> a[2005];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, s; cin >> s >> n;

    for(int i = 1; i <= n; ++i){
        cin >> v[i] >> w[i] >> k[i];
        k[i] = min(k[i], s / w[i]);

        int pw = 1;
        while (pw <= k[i]){
            a[w[i] * pw].push_back(v[i] * pw);
            k[i] -= pw;
        }

        if (k[i]){
            a[w[i] * k[i]].push_back(v[i] * k[i]);
        }
    }    

    for(int i = 1; i <= s; ++i){
        sort(a[i].begin(), a[i].end());
        while (!a[i].empty() && i * a[i].size() > s){
            a[i].pop_back();
        }
    }

    for(int w = 1; w <= s; ++w){
        for(int v : a[w]){
            for(int i = s; i >= w; --i){
                dp[i] = max(dp[i], dp[i - w] + v);
            }
        }
    }

    cout << dp[s];

    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:53:49: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |         while (!a[i].empty() && i * a[i].size() > s){
      |                                 ~~~~~~~~~~~~~~~~^~~

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