Submission #469494

#	Time	Username	Problem	Language	Result	Execution time	Memory
469494		Croco	Knapsack (NOI18_knapsack)	C++17	100 / 100	114 ms	35936 KiB

knapsack

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

using namespace std;

const int N = 5e5+5;

vector<pair<int,int>> item[2005];

int dp[2005][2005];

signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int s,n;
    cin>>s>>n;
    for(int i=0;i<n;i++)
    {
        int val,w,amt;
        cin>>val>>w>>amt;
        if(w <= s && amt > 0)
            item[w].push_back({val,amt});
    }
    for(int i=0;i<2005;i++)
        for(int j=0;j<2005;j++)
            dp[i][j] = INT32_MIN;
    dp[0][0] = 0;
    int ans = 0;
    for(int i=1;i<=s;i++)
    {
        sort(item[i].begin(),item[i].end(),greater<pair<int,int>>());
        for(int j=0;j<=s;j++)
        {
            dp[i][j] = dp[i-1][j];
            int copies = 0;
            int profit = 0;
            int at = 0;
            int used = 0;
            while((copies + 1)*i <= j && at < item[i].size())
            {
                copies++;
                profit += item[i][at].first;
                if(dp[i-1][j - copies*i] != INT32_MIN)
                {
                    dp[i][j] = max(dp[i][j],dp[i-1][j-copies*i] + profit);
                    ans = max(ans,dp[i][j]);
                }
                used++;
                if(used == item[i][at].second)
                {
                    used = 0;
                    at++;
                }
            }
        }
    }
    cout << ans;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:40:45: 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]
   40 |             while((copies + 1)*i <= j && at < item[i].size())
      |                                          ~~~^~~~~~~~~~~~~~~~

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