제출 #847836

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
847836		lolotica	Knapsack (NOI18_knapsack)	C++14	0 / 100	1 ms	1112 KiB

knapsack

#include <bits/stdc++.h>
#define pii pair<int,int>
const int inf=-1e9;

const int N=1e5+5;
using namespace std;
int dp[N][2005];
int s,n;
vector<pii>weight[2005];
int ans=inf;

int main()
{
    cin>>s>>n;
    for(int i=1; i<=n; i++)
    {
        int w,v,k;
        cin>>w>>v>>k;
        weight[w].push_back({v,k});

    }
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=s;j++)
            dp[i][j]=inf;
    }
    dp[0][0]=0;
    int pos=0;
    for(int i=1; i<=s; i++)
    {
        if(weight[i].size()==0) continue;
        else
        {  sort(weight[i].begin(),weight[i].end(),greater<pii>());
            pos++;
            for(int j=0; j<=s; j++)
            {
                dp[pos][j]=dp[pos-1][j];
                int cnt=0;
                int type=0;
                int cur=0;
                int add=0;
                while((cnt+1)*i<=j&&type<weight[i].size())
                {
                    cnt++;
                    add+=weight[i][type].first;
                    if(dp[pos-1][j-cnt*i]!=inf)
                    {
                        dp[pos][j]=max(dp[pos][j],dp[pos-1][j-cnt*i]+add);
                        ans=max(ans,dp[pos][j]);
                    }
                    cur++;
                    if(cur==weight[i][type].second)
                    {
                        type++;
                        cur=0;
                    }






                }
            }
        }
    }


cout<<ans;


    return 0;

}

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

knapsack.cpp: In function 'int main()':
knapsack.cpp:42:41: 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((cnt+1)*i<=j&&type<weight[i].size())
      |                                     ~~~~^~~~~~~~~~~~~~~~~

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