제출 #548567

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
548567		Alexandruabcde	Knapsack (NOI18_knapsack)	C++14	100 / 100	126 ms	3648 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 1e5 + 5;
constexpr int SUMMAX = 2005;
typedef long long LL;

struct Item {
    int value;
    int copies;

    bool operator < (const Item &other) const {
        return value > other.value;
    }
};

int S, N;

vector <Item> V[SUMMAX];
int dp[SUMMAX];

int main () {
    cin >> S >> N;

    for (int i = 1; i <= N; ++ i ) {
        Item it;
        int w;
        cin >> it.value >> w >> it.copies;

        V[w].push_back(it);
    }

    for (int i = 0; i <= S; ++ i )
        dp[i] = -1;
    dp[0] = 0;

    for (int w = 0; w <= S; ++ w ) {
        int ind = 0;

        sort(V[w].begin(), V[w].end());

        for (int cnt = 0; cnt * w < S; ++ cnt ) {
            if (ind >= V[w].size()) break;

            for (int s = S; s >= w; -- s )
                if (dp[s - w] != -1) dp[s] = max(dp[s], dp[s - w] + V[w][ind].value);

            V[w][ind].copies --;
            if (V[w][ind].copies == 0) ++ ind;
        }
    }

    int ans = 0;
    for (int i = 0; i <= S; ++ i )
        ans = max(ans, dp[i]);
    cout << ans << '\n';

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

knapsack.cpp: In function 'int main()':
knapsack.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             if (ind >= V[w].size()) break;
      |                 ~~~~^~~~~~~~~~~~~~

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