Submission #837186

#	Time	Username	Problem	Language	Result	Execution time	Memory
837186		rinho	Knapsack (NOI18_knapsack)	C++14	100 / 100	70 ms	35024 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;

const int Nmax = 2000;
const int MOD = 1000000007;
const long long INF = 1e18 + 7;

int maxwei, n;
vector<pair<int, int>> weight[Nmax + 3];
long long dp[Nmax + 3][Nmax + 3];

bool cmp(pair<int, int> x, pair<int, int> y){
    return x.first > y.first;
}

void in(){
    cin >> maxwei >> n;
    for(int i = 1; i <= n; i++){
        int val, wei, cnt; cin >> val >> wei >> cnt;
        weight[wei].push_back({val, cnt});
    }
}

void sol(){
    //dp[i][w] là giá trị lớn nhất có thể đạt đc khi xét đến i đồ vật đầu tiên và sử dụng w khối lượng
    memset(dp, -0x3f, sizeof dp);
    dp[0][0] = 0;
    int i = 1; // bản chất i giống curwei nhưng vì có những curwei trống ko sử dụng nên nếu curwei có sử dụng thì sẽ tăng biến i lên 1
    
    long long ans = -INF;
    for(int curwei = 1; curwei <= maxwei; curwei++){
        if(weight[curwei].empty()) continue;
        sort(weight[curwei].begin(), weight[curwei].end(), cmp);

        for(int w = 0; w <= maxwei; w++){
            dp[i][w] = dp[i - 1][w];
            int copies = 0; // tổng số lần sử dụng các đồ vật có khối lượng curwei
            int j = 0; // xét đến giá trị lớn thứ j
            int usedthiswei = 0; // số lần sử dụng giá trị lớn thứ j
            long long val = 0; // tổng giá trị thu được từ các đồ vật khối lượng curwei

            while(((copies + 1) * curwei <= w) &&  j < weight[curwei].size()){
                copies++;
                val += 0ll + weight[curwei][j].first;

                if(dp[i - 1][w - copies * curwei] > -INF){
                    dp[i][w] = max(dp[i][w], dp[i - 1][w - copies * curwei] + val);
                    ans = max(ans, dp[i][w]);
                }
                
                usedthiswei++;
                if(usedthiswei == weight[curwei][j].second){ 
                    // vì weight[curwei][j].second lưu số lượng đồ vật mang khối lượng curwei 
                    //và có giá trị lớn thứ j nên nếu usedthiswei từ 0 cộng đến khi bằng, 
                    //thì tại thời điểm bằng chúng ta xài hết số lượng đồ của weight[curwei][j] rồi
                    // chính vì vậy ta đổi qua giá trị lớn thứ j + 1 trong khối lượng curwei và reset biến usedthiswei = 0
                    usedthiswei = 0;
                    j++;
                }
            }
        }
        i++;
    }

    
    cout << ans << '\n';
}
int main(){
    //freopen(" ", "r", stdin);
    //freopen(" ", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
       in();
       sol();
    }
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void sol()':
knapsack.cpp:42:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             while(((copies + 1) * curwei <= w) &&  j < weight[curwei].size()){
      |                                                    ~~^~~~~~~~~~~~~~~~~~~~~~~

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