제출 #1105834

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1105834		vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	112 ms	36936 KiB

knapsack

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 2020;

int s,n;
int dp[maxn][maxn];
map<int,vector<pair<int,int>>> mp;

void solve()
{
    cin >> s >> n;
    int a,b,c;
    for(int i = 0; i < n; ++i)
    {
        cin >> a >> b >> c;
        if(b <= s && c > 0) mp[b].push_back({a,c});
    }
    for(int i = 0; i < maxn; ++i)
    {
        for(int j = 0; j < maxn; ++j) dp[i][j] = INT32_MIN;
    }
    dp[0][0] = 0;
    int cnt = 1;
    for(auto &[w, items] : mp)
    {
        sort(items.begin(),items.end(),greater<pair<int,int>>());
        for(int i = 0; i <= s; ++i)
        {
            dp[cnt][i] = dp[cnt - 1][i];
            int copies = 0;
            int type = 0;
            int used = 0;
            int add = 0;
            while((copies + 1) * w <= i && type < items.size())
            {
                copies++;
                add += items[type].first;
                if(dp[cnt - 1][i - copies * w] != INT32_MIN)
                {
                    dp[cnt][i] = max(dp[cnt][i],dp[cnt - 1][i - copies * w] + add);
                }
                used++;
                if(used == items[type].second)
                {
                    used = 0;
                    type++;
                }
            }
        }
        cnt++;
    }
    int ans = INT32_MIN;
    for(int i = 0; i < maxn; ++i)
    {
        for(int j = 0; j < maxn; ++j) ans = max(ans,dp[i][j]);
    }
    cout << ans << endl;
}

signed main()
{
    solve();
}

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

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

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