Submission #549629

#	Time	Username	Problem	Language	Result	Execution time	Memory
549629		aun5x	Knapsack (NOI18_knapsack)	C++14	100 / 100	249 ms	40504 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double db;
const int S = 2000+1;
const int N = 1e6;

ll dp [S][S]; // dp[i][j] = using the first i items with weight i to get the sum j; = max value obtained

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

int main()
{
    int s; int n;
    cin >> s >> n;
    set<pair<ll,ll>> v[S]; // v[weight] = { {value,index} ... }
    vector<int> k(n+1);

    for (int i = 1 ;i <= n ;i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        v[b].insert({a,i});
        k[i] = c;
    }
    ll ans = 0;
    for (int i = 1; i <= s; i++) // the weights 
    {        
        for (int j = 1; j <= s; j++) // the cost
        {
            dp[i][j] = dp[i-1][j];

            ll curr_w = 0; ll val = 0; ll cnt = 0;
            auto it = v[i].end();
            if (!v[i].empty()) it--;

            while (curr_w <= s && !v[i].empty())
            {
                pair<ll,ll> u = *it;
                val+= u.first; cnt++; curr_w += i;

                if (j-curr_w >= 0)
                {
                    dp[i][j] = max(
                        dp[i][j], dp[i-1][j-curr_w] + val
                    );
                }
                
            
                if (cnt == k[u.second]) 
                {
                    if (it == v[i].begin()) break;
                    it--;
                    cnt = 0;
                    
                }
            }
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans;

}   

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